The satisfiability threshold for randomly generated binary constraint satisfaction problems

DOI10.1007/B11961MaRDI QIDQ5900940zbMATH OpenOpenAlexFDO

Authors Alan Frieze, Michael Molloy

Publication date 26 May 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b11961

Mathematics Subject Classification ID

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

Recommendations

• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• Models for Random Constraint Satisfaction Problems
• Random constraint satisfaction: A more accurate picture
• The Resolution Complexity of Random Constraint Satisfaction Problems

Cited in

(7)

• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• A probabilistic analysis of randomly generated binary constraint satisfaction problems.
• On unique satisfiability and the threshold behavior of randomized reductions
• Many hard examples in exact phase transitions
• Threshold properties of random Boolean constraint satisfaction problems
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• The satisfiability threshold for randomly generated binary constraint satisfaction problems

This page was built for publication: The satisfiability threshold for randomly generated binary constraint satisfaction problems

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