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 satisfactionPolymorphismFrozen variable

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Hypertree decompositions and tractable queries
• List homomorphisms and circular arc graphs
• NP is as easy as detecting unique solutions
• Networks of constraints: Fundamental properties and applications to picture processing
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• Reasoning about qualitative temporal information
• Some optimal inapproximability results
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• 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 scaling window of the 2-SAT transition

Cited in

(4)

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

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)