The Resolution Complexity of Random Constraint Satisfaction Problems

DOI10.1137/S0097539703436485zbMath1139.68028OpenAlexW2104427163MaRDI QIDQ3507525

No author found.

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 transitionsharp thresholdrandom constraint satisfaction problemsrandom \(k\)-SATresolution complexity

Mathematics Subject Classification ID

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

Related Items (9)

Many hard examples in exact phase transitions ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ The satisfiability threshold for randomly generated binary constraint satisfaction problems ⋮ The solution space geometry of random linear equations ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ When does the giant component bring unsatisfiability? ⋮ Resolution complexity of random constraint satisfaction problems: Another half of the story ⋮ 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