Circuit satisfiability and constraint satisfaction around Skolem arithmetic
From MaRDI portal
Publication:1676359
DOI10.1016/J.TCS.2017.08.025zbMATH Open1380.68221OpenAlexW2752581169MaRDI QIDQ1676359FDOQ1676359
Authors: Christian Glaßer, Peter Jonsson, 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
Recommendations
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Satisfiability of algebraic circuits over sets of natural numbers
- Satisfiability of Algebraic Circuits over Sets of Natural Numbers
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
Cites Work
- Title not available (Why is that?)
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Title not available (Why is that?)
- On the complexity of H-coloring
- 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 temporal constraint satisfaction problems
- 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
- Cores of Countably Categorical Structures
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Title not available (Why is that?)
- The decision problem for exponential diophantine equations
- On the algebraic structure of combinatorial problems
- Essential convexity and complexity of semi-algebraic constraints
- Computational complexity of linear constraints over the integers
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computational completeness of equations over sets of natural numbers
- The complexity of membership problems for circuits over sets of natural numbers
- Complexity of equations over sets of natural numbers
- The complexity of membership problems for circuits over sets of integers
- On the complexity of integer programming
- Constraint Satisfaction Problems of Bounded Width
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
- Title not available (Why is that?)
- The computational complexity of logical theories
- Dichotomies for classes of homomorphism problems involving unary functions
- On direct products of theories
- The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
- Integer circuit evaluation is PSPACE-complete
- Title not available (Why is that?)
- Equivalence problems for circuits over sets of natural numbers
- Satisfiability of algebraic circuits over sets of natural numbers
- Complexity of Subcases of Presburger Arithmetic
- Dominoes and the complexity of subclasses of logical theories
- Functions definable by arithmetic circuits
Cited In (6)
- Satisfiability of algebraic circuits over sets of natural numbers
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Balance problems for integer circuits
- Balance problems for integer circuits
- Emptiness problems for integer circuits
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
This page was built for publication: Circuit satisfiability and constraint satisfaction around Skolem arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1676359)
