Resolution complexity of random constraint satisfaction problems: Another half of the story

DOI10.1016/J.DAM.2005.05.009MaRDI QIDQ2581550zbMATH OpenOpenAlexFDO

Authors Yong Gao, J. Culberson

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.05.009

zbMATH Keywords

Upper boundsResolution complexityRandom constraint satisfaction problems

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

• Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
• The Resolution Complexity of Random Constraint Satisfaction Problems
• A dichotomy theorem for the resolution complexity of random constraint satisfaction problems
• On the constraint length of random \(k\)-CSP
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem

Cites work

• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1946856 (Why is no real title available?)
• scientific article; zbMATH DE number 1754601 (Why is no real title available?)
• A perspective on certain polynomial-time solvable classes of satisfiability
• A threshold for unsatisfiability
• Approximating the unsatisfiability threshold of random formulas
• Lower bounds for random 3-SAT via differential equations
• Models and thresholds for random constraint satisfaction problems
• Random constraint satisfaction: Flaws and structure
• Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
• Rigorous results for random (\(2+p)\)-SAT
• The Resolution Complexity of Random Constraint Satisfaction Problems
• The phase transition in a random hypergraph
• Upper bounds on the satisfiability threshold

Cited in

(4)

• The Resolution Complexity of 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
• Spines of random constraint satisfaction problems: definition and connection with computational complexity

This page was built for publication: Resolution complexity of random constraint satisfaction problems: Another half of the story

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