Integer Circuit Evaluation Is PSPACE-Complete

摘要

K. W. Wagner (1984, Technical report N/84/52, Friedrich–Schiler-Universität Jena) introduced the integer circuit evaluation problem. Informally, the problem concerns a circuit that takes singleton sets, each containing one integer, and combines them using three types of set operations: A∪B, A ⊗B={a·b∣a∈A, b∈B}, and A⊗B={a+b∣a∈A, b∈B}. The problem is to determine whether the set output by the circuit contains a particular integer. In this paper we show that the integer circuit problem is PSPACE-complete, resolving an open problem posed by P. McKenzie, H. Vollmer, and K. W. Wagner (2000, in “Proceedings of the 2000 FSTTCS conference, New Delhi, India, December).