Recognizing frozen variables in constraint satisfaction problems

DOI10.1016/J.TCS.2004.08.006MaRDI QIDQ706617zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Andrei 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 satisfactionFrozen variablePolymorphism

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of unfrozen problems
• Frozen variables in random Boolean constraint satisfaction problems
• Classifying the Complexity of Constraints Using Finite Algebras
• Random formulas have frozen variables
• scientific article; zbMATH DE number 1670830

Cites work

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

Cited in

(4)

• On the freezing of variables in random constraint satisfaction problems
• On the complexity of unfrozen problems
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Computational complexity of auditing finite attributes in statistical databases

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

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