Emptiness problems for integer circuits

DOI10.4230/LIPICS.MFCS.2017.33MaRDI QIDQ5111247zbMATH OpenOpenAlexFDO

Authors Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

Publication date 26 May 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/mfcs/mfcs2017.html#BarthBDGMT17

zbMATH Keywords

computational complexityinteger circuitsinteger expressionspolynomial identity testing

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Emptiness problems for integer circuits
• 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 Positive Numbers
• The complexity of membership problems for circuits over sets of natural numbers

Cites work

• A Decision Procedure for the First Order Theory of Real Addition with Order
• Arithmetic circuits: a survey of recent results and open questions
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Dominoes and the complexity of subclasses of logical theories
• Emptiness problems for integer circuits
• Equivalence problems for circuits over sets of natural numbers
• Functions definable by arithmetic circuits
• scientific article; zbMATH DE number 3874608 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (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 2079409 (Why is no real title available?)
• scientific article; zbMATH DE number 1827828 (Why is no real title available?)
• scientific article; zbMATH DE number 2115010 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• Integer circuit evaluation is PSPACE-complete
• Parallel identity testing for skew circuits with big powers and applications
• PRIMES is in P
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Progress on polynomial identity testing
• Progress on polynomial identity testing. II
• Relationships among $PL$, $\#L$, and the determinant
• Satisfiability of algebraic 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 natural numbers
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• The computational complexity of logical theories
• The decision problem for exponential diophantine equations
• The difference and truth-table hierarchies for NP

Cited in

(5)

• Emptiness problems for integer circuits
• Balance problems for integer circuits
• A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. II: The main reduction
• Balance problems for integer circuits
• Emptiness problems for integer circuits

This page was built for publication: Emptiness problems for integer circuits

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