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

DOI10.1016/J.DAM.2005.05.009zbMATH Open1090.68100OpenAlexW2110254595MaRDI QIDQ2581550FDOQ2581550

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

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

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)

Cites Work

• Approximating the unsatisfiability threshold of random formulas
• The phase transition in a random hypergraph
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Random constraint satisfaction: Flaws and structure
• Models and thresholds for random constraint satisfaction problems
• Title not available (Why is that?)
• Lower bounds for random 3-SAT via differential equations
• A threshold for unsatisfiability
• A perspective on certain polynomial-time solvable classes of satisfiability
• Rigorous results for random (\(2+p)\)-SAT
• Title not available (Why is that?)
• Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
• Title not available (Why is that?)
• 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)