文章基本信息

标题：Integer Circuit Evaluation is PSPACE-complete
本地全文：下载
作者：Ke Yang
期刊名称：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