期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper, we address the problem of evaluating the
Integer Circuit (IC), or the + -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.
关键词：Keywords:
Chinese Remainder Theorem, Integer Circuit, PSPACE, Quantified Boolean Circuit
