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 complexitypolynomial identity testinginteger expressionsinteger circuits

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Integer circuit evaluation is PSPACE-complete
• PRIMES is in P
• Parallel identity testing for skew circuits with big powers and applications
• 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 Positive 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 computational complexity of logical theories
• The decision problem for exponential diophantine equations
• The difference and truth-table hierarchies for NP

Cited in

(5)

• A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. II: The main reduction
• Emptiness problems for integer circuits
• Balance problems for integer circuits
• 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)