Độ Phức Tạp của Các Bài Toán Thành Viên cho Mạch qua Tập Hợp Số Tự Nhiên

Vấn đề kiểm tra tính thành viên trong một tập con của các số tự nhiên được tạo ra tại đầu ra của một mạch kết hợp được chỉ ra là nắm bắt một phạm vi rộng lớn của các lớp độ phức tạp. Mặc dù vấn đề chung vẫn còn mở, trường hợp $$\bigcup, \bigcap, +, \times$$ được chứng minh là hoàn hảo NEXPTIME, các trường hợp $$\bigcup, \bigcap, ^-, \times$$, $$\bigcup, \bigcap, \times$$, $$\bigcup, \bigcap, +$$ được chứng minh là hoàn hảo PSPACE, trường hợp $$\bigcup, +$$ được chứng minh là hoàn hảo NP, trường hợp {∩, +} được chứng minh là hoàn hảo C=L, và một số trường hợp khác đã được giải quyết. Những bài toán phụ trợ thú vị được sử dụng, chẳng hạn như kiểm tra tính không rỗng cho các mạch hợp nhất-giao nhau-nối tiếp, và biểu diễn mỗi số nguyên, được lấy từ một tập hợp cho trước như đầu vào, dưới dạng các lũy thừa của các số nguyên nguyên tố tương đối mà người ta chọn. Kết quả của chúng tôi mở rộng theo những cách không tầm thường các công trình trước đó của Stockmeyer và Meyer (1973), Wagner (1984) và Yang (2000).