Satisfiability of algebraic circuits over sets of natural numbers

DOI10.1016/J.DAM.2010.04.001MaRDI QIDQ987688zbMATH OpenOpenAlexFDO

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

Publication date 13 August 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.04.001

zbMATH Keywords

computational complexitysatisfiability problemscombinatorial integer circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analytic circuit theory (94C05)

Recommendations

• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• Equivalence Problems for Circuits over Sets of Natural Numbers
• Equivalence problems for circuits over sets of natural numbers
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• The complexity of membership problems for circuits over sets of natural numbers
• scientific article; zbMATH DE number 1962845
• Computational completeness of equations over sets of natural numbers
• On the Computational Completeness of Equations over Sets of Natural Numbers
• Publication:4729350

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 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1962845 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• Equivalence Problems for Circuits over Sets of Natural Numbers
• PRIMES is in P
• The decision problem for exponential diophantine equations

Cited in

(13)

• Parsing Boolean grammars over a one-letter alphabet using online convolution
• Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Satisfiability in multi-valued circuits
• Balance problems for integer circuits
• Balance problems for integer circuits
• Complex algebras of arithmetic
• Computational completeness of equations over sets of natural numbers
• Emptiness problems for integer circuits
• Emptiness problems for integer circuits
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems

This page was built for publication: Satisfiability of algebraic 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 Q987688)