The complexity of membership problems for circuits over sets of natural numbers
From MaRDI portal
Publication:2474202
DOI10.1007/s00037-007-0229-6zbMath1133.68028OpenAlexW2765659955MaRDI QIDQ2474202
Pierre McKenzie, Klaus W. Wagner
Publication date: 5 March 2008
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-007-0229-6
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Equations over sets of integers with addition only, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States, A Characterization of NP Within Interval-Valued Computing, Emptiness problems for integer circuits, Unnamed Item, Complexity of equations over sets of natural numbers, Extensions of dynamic programming for multi-stage combinatorial optimization, One-nonterminal conjunctive grammars over a unary alphabet, Unambiguous conjunctive grammars over a one-symbol alphabet, Computational completeness of equations over sets of natural numbers, Functions Definable by Arithmetic Circuits, Representing hyper-arithmetical sets by equations over sets of integers, Equivalence problems for circuits over sets of natural numbers, Parsing Boolean grammars over a one-letter alphabet using online convolution, Least and greatest solutions of equations over sets of integers, ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS, On Equations over Sets of Numbers and Their Limitations, One-Nonterminal Conjunctive Grammars over a Unary Alphabet, Emptiness Problems for Integer Circuits, Balance problems for integer circuits, Monomials in arithmetic circuits: complete problems in the counting hierarchy
