Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR00-012 | 14th February 2000 00:00

#### Integer Circuit Evaluation is PSPACE-complete

TR00-012
Authors: Ke Yang
Publication: 25th February 2000 00:10
Downloads: 2979
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