Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic

DOI10.1007/978-3-319-40189-8_33zbMath1475.68123OpenAlexW2486394533MaRDI QIDQ3188272

Christian Glaßer, Barnaby Martin, Peter Jonsson

Publication date: 17 August 2016

Published in: Pursuit of the Universal (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/22848/1/22848.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) First-order arithmetic and fragments (03F30) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items

Constraint Satisfaction Problems over Numeric Domains ⋮ Emptiness Problems for Integer Circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Computational complexity of linear constraints over the integers
• Complexity of equations over sets of natural numbers
• The complexity of membership problems for circuits over sets of integers
• Satisfiability of algebraic circuits over sets of natural numbers
• On the complexity of H-coloring
• The computational complexity of logical theories
• Dichotomies for classes of homomorphism problems involving unary functions
• Computational completeness of equations over sets of natural numbers
• Equivalence problems for circuits over sets of natural numbers
• The complexity of membership problems for circuits over sets of natural numbers
• Schaefer's Theorem for Graphs
• Essential Convexity and Complexity of Semi-Algebraic Constraints
• Constraint Satisfaction Problems over the Integers with Successor
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Functions Definable by Arithmetic Circuits
• The complexity of temporal constraint satisfaction problems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Constraint Satisfaction Problems of Bounded Width
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• On direct products of theories
• Integer circuit evaluation is PSPACE-complete