| Abstract |
|
In this paper, we address the problem of evaluating the Integer Circuit (IC), or the {cup, times, +}-circuit over the set of natural numbers. The problem is a natural extension to the integer expression by Stockmeyer and Mayer, and is studied by Mckenzie, Vollmer and Wagner in their “Polynomial Replacement System”. We show a polynomial-time algorithm that reduces QBF (Quantified Boolean Formula) problem to the Integer Circuit problem. This complements the result of Wagner to show that IC problem is PSPACE-complete. The proof in this paper provides a new perspective to describe PSPACE-completeness.
|
 Additional Information
|
Index Terms- Integer Circuit, PSPACE, Chinese Remainder Theorem
Citation:
Ke Yang,
"Integer Circuit Evaluation is PSPACE-Complete,"
coco,
p. 204,
15th Annual IEEE Conference on Computational Complexity (CoCo'00),
2000
|
