The complexity of membership problems for circuits over sets of natural numbers

DOI10.1007/3-540-36494-3_50MaRDI QIDQ4418682zbMATH OpenFDO

Authors Pierre McKenzie, K. W. Wagner

Publication date 11 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2607/26070571.htm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of membership problems for circuits over sets of natural numbers
• The complexity of membership problems for circuits over sets of integers
• The complexity of membership problems for circuits over sets of integers
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Equivalence problems for circuits over sets of natural numbers

Cited in

(15)

• Equivalence problems for circuits over sets of natural numbers
• Balance problems for integer circuits
• The complexity of membership problems for circuits over sets of natural numbers
• Polynomial-space decidable membership problems for recurrent systems over sets of natural numbers
• Equivalence Problems for Circuits over Sets of Natural Numbers
• Functions definable by arithmetic circuits
• Balance problems for integer circuits
• Complex algebras of arithmetic
• The complexity of membership problems for circuits over sets of integers
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• Fundamentals of Computation Theory
• Integer circuit evaluation is PSPACE-complete
• The complexity of membership problems for circuits over sets of integers
• Satisfiability of algebraic circuits over sets of natural numbers

This page was built for publication: The complexity of membership problems for circuits over sets of natural numbers

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