Complexity-theoretic models of phase transitions in search problems

DOI10.1016/S0304-3975(00)00061-XMaRDI QIDQ1583531zbMATH OpenFDO

Authors Paul E. Dunne, A. Gibbons, Michele Zito

Publication date 26 October 2000

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

zbMATH Keywords

computational complexitysearch problemsphase-transitions

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Refining the phase transition in combinatorial search
• scientific article; zbMATH DE number 1369843
• Random instances of problems in NP -- algorithms and statistical physics
• Phase transitions and the search problem
• scientific article; zbMATH DE number 67483

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 3549021 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• Approximating the unsatisfiability threshold of random formulas (extended abstract)
• Average Case Complete Problems
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Every monotone graph property has a sharp threshold
• Hard random 3-SAT problems and the Davis-Putnam procedure
• On the greedy algorithm for satisfiability
• Phase transitions and the search problem
• Some Examples of Combinatorial Averaging
• The hardest constraint problems: A double phase transition
• The satisfiability constraint gap
• Threshold functions

Cited in

(15)

• scientific article; zbMATH DE number 1946856 (Why is no real title available?)
• Phase transitions of EXPSPACE-complete problems: a further step
• Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• Phase transitions and the search problem
• Typical case complexity and phase transitions. Papers from the workshop, Ottawa, ON, Canada, May 14--16, 2003
• scientific article; zbMATH DE number 4140654 (Why is no real title available?)
• Refining the phase transition in combinatorial search
• A model for phase transition of random answer-set programs
• Phase transitions of PP-complete satisfiability problems. (Abstract)
• scientific article; zbMATH DE number 3862491 (Why is no real title available?)
• Phase transitions of EXPSPACE-complete problems
• Determining computational complexity from characteristic ``phase transitions
• Random instances of problems in NP -- algorithms and statistical physics
• The complexity of contract negotiation

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)