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

DOI10.4230/LIPICS.MFCS.2016.32zbMATH Open1398.68227OpenAlexW2547722307MaRDI QIDQ4608591FDOQ4608591

Authors: Titus Dose 

Publication date: 21 March 2018

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

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

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)

Cited In (10)

• Title not available (Why is that?)
• 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)