Circuit satisfiability and constraint satisfaction around Skolem arithmetic
type: Item
instance of: scholarly article
title: Circuit satisfiability and constraint satisfaction around Skolem arithmetic
zbMATH Open document ID: 1380.68221
author: Christian Glaßer
author: Peter Jonsson
author: Barnaby Martin
published in: Theoretical Computer Science
publication date: 2017-11-07T00:00:00Z
full work available at URL: 22848.pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 6803370
zbMATH Keywords: circuit satisfiability
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: Skolem arithmetic
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
OpenAlex ID: W2752581169
cites work: Satisfiability of algebraic circuits over sets of natural numbers
cites work: On direct products of theories
cites work: Q4781602
cites work: The complexity of homomorphism and constraint satisfaction problems seen from the other side
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: The complexity of satisfiability problems
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: On the complexity of H-coloring
cites work: The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Non-dichotomies in Constraint Satisfaction Complexity
cites work: The complexity of temporal constraint satisfaction problems
cites work: Schaefer's theorem for graphs
cites work: Constraint Satisfaction Problems over the Integers with Successor
cites work: Essential Convexity and Complexity of Semi-Algebraic Constraints
cites work: Q4131648
cites work: Q3340148
cites work: Integer circuit evaluation is PSPACE-complete
cites work: The complexity of membership problems for circuits over sets of natural numbers
cites work: The complexity of membership problems for circuits over sets of integers
cites work: The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
cites work: Equivalence problems for circuits over sets of natural numbers
cites work: Functions Definable by Arithmetic Circuits
cites work: Complexity of equations over sets of natural numbers
cites work: Computational completeness of equations over sets of natural numbers
cites work: Cores of Countably Categorical Structures
cites work: Dichotomies for classes of homomorphism problems involving unary functions
cites work: On the algebraic structure of combinatorial problems
cites work: Q5573961
cites work: Q4298260
cites work: A Decision Procedure for the First Order Theory of Real Addition with Order
cites work: The computational complexity of logical theories
cites work: Q5613949
cites work: The decision problem for exponential diophantine equations
cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations
cites work: On the complexity of integer programming
cites work: Complexity of Subcases of Presburger Arithmetic
cites work: Dominoes and the complexity of subclasses of logical theories
cites work: Q3818127
cites work: Computational complexity of linear constraints over the integers
cites work: Constraint Satisfaction Problems of Bounded Width
cites work: Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
DOI: 10.1016/J.TCS.2017.08.025
description: scientific article; zbMATH DE number 6803370