Recognizing frozen variables in constraint satisfaction problems

DOI10.1016/J.TCS.2004.08.006zbMATH Open1086.68056OpenAlexW1968063049MaRDI QIDQ706617FDOQ706617

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

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

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)

Cites Work

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

Cited In (4)

• On the complexity of unfrozen problems
• On the freezing of variables in random constraint satisfaction problems
• Computational complexity of auditing finite attributes in statistical databases
• 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)