scientific article; zbMATH DE number 1962845

MaRDI QIDQ4418682zbMATH OpenFDO

Authors Pierre McKenzie, K. W. Wagner

Publication date 11 August 2003

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

Mathematics Subject Classification ID

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

Recommendations

• The complexity of membership problems for circuits over sets of natural numbers
• Mathematical Foundations of Computer Science 2004
• 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)

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

This page was built for publication:

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