Complexity-theoretic models of phase transitions in search problems
From MaRDI portal
Publication:1583531
DOI10.1016/S0304-3975(00)00061-XzbMATH Open0949.68058MaRDI QIDQ1583531FDOQ1583531
A. Gibbons, Paul E. Dunne, Michele Zito
Publication date: 26 October 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Every monotone graph property has a sharp threshold
- Title not available (Why is that?)
- A Computing Procedure for Quantification Theory
- The hardest constraint problems: A double phase transition
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Threshold functions
- Title not available (Why is that?)
- Hard random 3-SAT problems and the Davis-Putnam procedure
- Average Case Complete Problems
- Some Examples of Combinatorial Averaging
- On the greedy algorithm for satisfiability
- Phase transitions and the search problem
- The satisfiability constraint gap
- Approximating the unsatisfiability threshold of random formulas (Extended Abstract)
Cited In (7)
- Title not available (Why is that?)
- Typical case complexity and phase transitions. Papers from the workshop, Ottawa, ON, Canada, May 14--16, 2003
- Title not available (Why is that?)
- Phase transitions of PP-complete satisfiability problems. (Abstract)
- Title not available (Why is that?)
- The complexity of contract negotiation
- Title not available (Why is that?)
This page was built for publication: Complexity-theoretic models of phase transitions in search problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583531)
