Integer circuit evaluation is PSPACE-complete

DOI10.1006/JCSS.2001.1768MaRDI QIDQ5956016zbMATH OpenOpenAlexFDO

Authors Ke Yang

Publication date 19 February 2002

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/c58e32f7ae7b2b98aff91ab10c1a076c0c25d286

zbMATH Keywords

PSPACE-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of membership problems for circuits over sets of integers
• Mathematical Foundations of Computer Science 2004
• The complexity of membership problems for circuits over sets of natural numbers
• scientific article; zbMATH DE number 1962845
• Emptiness problems for integer circuits

Cites work

• Arithmetization: A new method in structural complexity theory
• Finite Monoids: From Word to Circuit Evaluation
• scientific article; zbMATH DE number 3830444 (Why is no real title available?)
• scientific article; zbMATH DE number 3874609 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2080200 (Why is no real title available?)
• scientific article; zbMATH DE number 3221503 (Why is no real title available?)
• Non-commutative arithmetic circuits: depth reduction and size lower bounds

Cited in

(9)

• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Emptiness problems for integer circuits
• Balance problems for integer circuits
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Balance problems for integer circuits
• Emptiness problems for integer circuits
• Complexity of equations over sets of natural numbers
• Arithmetic circuits with division
• RNA: R1CS normalization algorithm based on data flow graphs for zero-knowledge proofs

This page was built for publication: Integer circuit evaluation is PSPACE-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956016)