Circuit satisfiability and constraint satisfaction around Skolem arithmetic

DOI10.1016/j.tcs.2017.08.025zbMath1380.68221OpenAlexW2752581169MaRDI QIDQ1676359

Peter Jonsson, Christian Glaßer, Barnaby Martin

Publication date: 7 November 2017

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

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

zbMATH Keywords

computational complexityconstraint satisfactionSkolem arithmeticcircuit satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) First-order arithmetic and fragments (03F30)

Related Items (3)

Emptiness problems for integer circuits ⋮ Unnamed Item ⋮ Balance problems for integer circuits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Dominoes and the complexity of subclasses of logical theories
• The decision problem for exponential diophantine equations
• The computational complexity of logical theories
• On the algebraic structure of combinatorial problems
• 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
• Complexity of Subcases of Presburger Arithmetic
• Constraint Satisfaction Problems over the Integers with Successor
• Non-dichotomies in Constraint Satisfaction Complexity
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• 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)
• On the complexity of integer programming
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• A Decision Procedure for the First Order Theory of Real Addition with Order
• 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
• Cores of Countably Categorical Structures
• 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

This page was built for publication: Circuit satisfiability and constraint satisfaction around Skolem arithmetic