Recognizing frozen variables in constraint satisfaction problems

DOI10.1016/j.tcs.2004.08.006zbMath1086.68056OpenAlexW1968063049MaRDI QIDQ706617

Peter Jonsson, Andrei A. Krokhin

Publication date: 9 February 2005

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.08.006

zbMATH Keywords

Computational complexityConstraint satisfactionPolymorphismFrozen variable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

Computational complexity of auditing finite attributes in statistical databases ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• The complexity of facets (and some facets of complexity)
• NP is as easy as detecting unique solutions
• On the complexity of H-coloring
• The complexity of facets resolved
• Reasoning about qualitative temporal information
• On the algebraic structure of combinatorial problems
• How to determine the expressive power of constraints
• Auditing Boolean attributes
• Conjunctive-query containment and constraint satisfaction
• Networks of constraints: Fundamental properties and applications to picture processing
• List homomorphisms and circular arc graphs
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The scaling window of the 2-SAT transition
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Bi‐arc graphs and the complexity of list homomorphisms
• The complexity of maximal constraint languages
• Computer Science Logic
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Some optimal inapproximability results
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Frozen development in graph coloring

This page was built for publication: Recognizing frozen variables in constraint satisfaction problems