Complexity-theoretic models of phase transitions in search problems

DOI10.1016/S0304-3975(00)00061-XzbMath0949.68058MaRDI QIDQ1583531

Alan M. Gibbons, Paul E. Dunne, Michele Zito

Publication date: 26 October 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexityphase-transitionssearch problems

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

The complexity of contract negotiation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Threshold functions
• On the greedy algorithm for satisfiability
• The hardest constraint problems: A double phase transition
• Phase transitions and the search problem
• The satisfiability constraint gap
• Hard random 3-SAT problems and the Davis-Putnam procedure
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Some Examples of Combinatorial Averaging
• Average Case Complete Problems
• Approximating the unsatisfiability threshold of random formulas (Extended Abstract)
• Every monotone graph property has a sharp threshold
• A Computing Procedure for Quantification Theory