The Resolution Complexity of Random Constraint Satisfaction Problems

DOI10.1137/S0097539703436485MaRDI QIDQ3507525zbMATH OpenOpenAlexFDO

Authors

Publication date 19 June 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539703436485

zbMATH Keywords

phase transitionrandom \(k\)-SATrandom constraint satisfaction problemsresolution complexitysharp threshold

Mathematics Subject Classification ID

Complexity of proofs (03F20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A dichotomy theorem for the resolution complexity of random constraint satisfaction problems
• Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
• Resolution complexity of random constraint satisfaction problems: Another half of the story
• A sharp threshold for a random constraint satisfaction problem
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem

Cited in

(25)

• When does the giant component bring unsatisfiability?
• Upper and lower bounds on the complexity of generalised resolution and generalised constraint satisfaction problems
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• An average analysis of backtracking on random constraint satisfaction problems
• On the constraint length of random \(k\)-CSP
• Many hard examples in exact phase transitions
• On the freezing of variables in random constraint satisfaction problems
• Resolution complexity of random constraint satisfaction problems: Another half of the story
• A dichotomy theorem for the resolution complexity of random constraint satisfaction problems
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
• Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
• Many hard examples for resolution
• A general model and thresholds for random constraint satisfaction problems
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• scientific article; zbMATH DE number 408796 (Why is no real title available?)
• Models for Random Constraint Satisfaction Problems
• The solution space geometry of random linear equations
• scientific article; zbMATH DE number 7301529 (Why is no real title available?)
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Random constraint satisfaction: Flaws and structure
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• Spines of random constraint satisfaction problems: definition and connection with computational complexity

This page was built for publication: The Resolution Complexity of Random Constraint Satisfaction Problems

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