Satisfiability of Algebraic Circuits over Sets of Natural Numbers

DOI10.1007/978-3-540-77050-3_21MaRDI QIDQ5458839zbMATH OpenOpenAlexFDO

Authors Christian Glaßer, Christian Reitwießner, Stephen Travers, Matthias Waldherr

Publication date 24 April 2008

Published in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77050-3_21

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Satisfiability of algebraic circuits over sets of natural numbers
• scientific article; zbMATH DE number 1962845
• The complexity of membership problems for circuits over sets of natural numbers
• Equivalence problems for circuits over sets of natural numbers
• Equivalence Problems for Circuits over Sets of Natural Numbers

Cites work

• Equivalence Problems for Circuits over Sets of Natural Numbers
• 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 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1962845 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• PRIMES is in P
• Reducibility among combinatorial problems
• The complexity of theorem-proving procedures
• The decision problem for exponential diophantine equations

Cited in

(6)

• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Computational completeness of equations over sets of natural numbers
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Functions definable by arithmetic circuits
• Satisfiability of algebraic circuits over sets of natural numbers

This page was built for publication: Satisfiability of Algebraic 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 Q5458839)