Approximating the unsatisfiability threshold of random formulas: (Extended abstract)Public Deposited
Downloadable ContentDownload PDF
- Resource Type
Let φ be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number such that if the ratio of the number of clauses over the number of variables of φ strictly exceeds κ, then φ is almost certainly unsatisfiable. By a well known and more or less straightforward argument, it can be shown that κ 3.
- Kirousis, L.M. (Lefteris M.), Kranakis, E, & Krizanc, D. (Danny). (1996). Approximating the unsatisfiability threshold of random formulas: (Extended abstract). doi:10.1007/3-540-61680-2_44
- Date Created
- In Collection: