2+p-SAT: Relation of typical-case complexity to the nature of the phase transition
- 20 October 1999
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 15 (3-4) , 414-435
- https://doi.org/10.1002/(sici)1098-2418(199910/12)15:3/4<414::aid-rsa10>3.0.co;2-g
Abstract
No abstract availableKeywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Renormalization group theory: Its basis and formulation in statistical physicsReviews of Modern Physics, 1998
- On the complexity of unsatisfiability proofs for random k-CNF formulasPublished by Association for Computing Machinery (ACM) ,1998
- Statistical mechanics of the random-satisfiability modelPhysical Review E, 1997
- A Threshold for UnsatisfiabilityJournal of Computer and System Sciences, 1996
- Entropy of theK-Satisfiability ProblemPhysical Review Letters, 1996
- Critical behavior in the computational cost of satisfiability testingArtificial Intelligence, 1996
- Critical Behavior in the Satisfiability of Random Boolean ExpressionsScience, 1994
- Optimization by Simulated AnnealingScience, 1983
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960