Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.

DOI10.4230/LIPICS.MFCS.2016.32MaRDI QIDQ4608591zbMATH OpenOpenAlexFDO

Authors Titus Dose

Publication date 21 March 2018

Full work available at URL https://dblp.uni-trier.de/db/conf/mfcs/mfcs2016.html#Dose16

zbMATH Keywords

computational complexityconstraint satisfaction problemsinteger expressions and circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Complexity of the counting constraint satisfaction problem
• Computational Complexity of Constraint Satisfaction
• The complexity of the counting constraint satisfaction problem
• The Complexity of the Counting Constraint Satisfaction Problem
• Constraint satisfaction problems: complexity and algorithms
• The complexity of constraint satisfaction revisited
• The complexity of recursive constraint satisfaction problems
• Constraint satisfaction -- algorithms and complexity analysis
• The approximability of constraint satisfaction problems
• The complexity of constraint satisfaction: an algebraic approach

Cited in

(10)

• scientific article; zbMATH DE number 6146470 (Why is no real title available?)
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Constraint satisfaction problems over the integers with successor
• Constraint satisfaction problems over numeric domains
• Balance problems for integer circuits
• Balance problems for integer circuits
• Emptiness problems for integer circuits
• Emptiness problems for integer circuits

This page was built for publication: Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608591)