Equivalence problems for circuits over sets of natural numbers

DOI10.1007/S00224-008-9144-8MaRDI QIDQ2268343zbMATH OpenOpenAlexFDO

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

Publication date 5 March 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9144-8

zbMATH Keywords

algorithmscombinatorial integer circuitscomputational complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Equivalence Problems for Circuits over Sets of Natural Numbers
• The complexity of membership problems for circuits over sets of natural numbers
• scientific article; zbMATH DE number 1962845
• Mathematical Foundations of Computer Science 2004
• The complexity of membership problems for circuits over sets of integers

Cites work

• Adaptive logspace reducibility and parallel time
• 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 3637287 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• Relationships among $PL$, $\#L$, and the determinant
• Some observations on the probabilistic algorithms and NP-hard problems
• 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

Cited in

(17)

• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Emptiness problems for integer circuits
• Computational completeness of equations over sets of natural numbers
• Balance problems for integer circuits
• The complexity of membership problems for circuits over sets of natural numbers
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Equivalence Problems for Circuits over Sets of Natural Numbers
• scientific article; zbMATH DE number 1962845 (Why is no real title available?)
• scientific article; zbMATH DE number 6146470 (Why is no real title available?)
• Balance problems for integer circuits
• Emptiness problems for integer circuits
• Mathematical Foundations of Computer Science 2004
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• Arithmetic circuits with division
• Parsing Boolean grammars over a one-letter alphabet using online convolution
• Satisfiability of algebraic circuits over sets of natural numbers

This page was built for publication: Equivalence 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 Q2268343)