The complexity of membership problems for circuits over sets of integers

DOI10.1016/J.TCS.2006.08.017MaRDI QIDQ861262zbMATH OpenOpenAlexFDO

Authors Stephen Travers

Publication date 9 January 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.08.017

zbMATH Keywords

arithmetic circuitscombinational circuitscompletenesscomputational complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 1962845
• The complexity of membership problems for circuits over sets of natural numbers
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Emptiness problems for integer circuits

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3874608 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1962845 (Why is no real title available?)
• Maze recognizing automata and nondeterministic tape complexity
• Nondeterministic Space is Closed under Complementation
• The method of forced enumeration for nondeterministic automata
• The twenty-fourth Fermat number is composite

Cited in

(32)

• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Evaluation of circuits over nilpotent and polycyclic groups
• Emptiness problems for integer circuits
• Extensions of dynamic programming for multi-stage combinatorial optimization
• Equivalence problems for circuits over sets of natural numbers
• Balance problems for integer circuits
• Reachability in two-clock timed automata is PSPACE-complete
• The complexity of membership problems for circuits over sets of natural numbers
• A lower bound for the coverability problem in acyclic pushdown VAS
• Equations over sets of integers with addition only
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• The odds of staying on budget
• Equivalence Problems for Circuits over Sets of Natural Numbers
• Functions definable by arithmetic circuits
• scientific article; zbMATH DE number 1962845 (Why is no real title available?)
• Balance problems for integer circuits
• Emptiness problems for integer circuits
• Life is random, time is not: Markov decision processes with window objectives
• Mathematical Foundations of Computer Science 2004
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Life is random, time is not: Markov decision processes with window objectives
• Percentile queries in multi-dimensional Markov decision processes
• Integer circuit evaluation is PSPACE-complete
• Least and greatest solutions of equations over sets of integers
• Parallel algorithms for power circuits and the word problem of the Baumslag group
• On the complexity of CSP-based ideal membership problems
• Complexity of equations over sets of natural numbers
• Multi-weighted reachability games
• As soon as possible but rationally
• Arithmetic circuits with division
• Representing hyper-arithmetical sets by equations over sets of integers
• Reachability games and friends: a journey through the Lens of memory and complexity (invited talk)

This page was built for publication: The complexity of membership problems for circuits over sets of integers

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