Equivalence problems for circuits over sets of natural numbers

DOI10.1007/s00224-008-9144-8zbMath1183.68308OpenAlexW2044079618MaRDI QIDQ2268343

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

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

algorithmscomputational complexitycombinatorial integer circuits

Mathematics Subject Classification ID

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

Related Items

Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Emptiness problems for integer circuits, Unnamed Item, Parsing Boolean grammars over a one-letter alphabet using online convolution, Emptiness Problems for Integer Circuits, Balance problems for integer circuits

Cites Work

• The complexity of membership problems for circuits over sets of integers
• Some observations on the probabilistic algorithms and NP-hard problems
• The complexity of membership problems for circuits over sets of natural numbers
• Adaptive logspace reducibility and parallel time
• Relationships among $PL$, $\#L$, and the determinant
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item