Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story

DOI10.1016/S1571-0653(04)00460-3zbMath1179.68142OpenAlexW2176203587MaRDI QIDQ3439112

Yong Gao, Joseph C. Culberson

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s1571-0653(04)00460-3

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Many hard examples in exact phase transitions ⋮ Resolution complexity of random constraint satisfaction problems: Another half of the story

Cites Work

• Unnamed Item
• The phase transition in a random hypergraph
• A perspective on certain polynomial-time solvable classes of satisfiability
• Models and thresholds for random constraint satisfaction problems
• Approximating the unsatisfiability threshold of random formulas
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: Flaws and structure
• Lower bounds for random 3-SAT via differential equations
• Upper bounds on the satisfiability threshold