Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-012 | 14th February 2000 00:00

Integer Circuit Evaluation is PSPACE-complete

RSS-Feed




TR00-012
Authors: Ke Yang
Publication: 25th February 2000 00:10
Downloads: 3728
Keywords: 


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 also 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 \cite{W84} to show
that IC problem is PSPACE-complete. The proof in this paper provides a
new perspective to describe PSPACE-completeness.



ISSN 1433-8092 | Imprint