Satisfiability Coding Lemma
| Author(s) : | Francis Zane Pavel Pudlak Ramamohan Paturi, |
| Publisher : | N/A |
| Publication Date : | 1997 |
| ISSN : | N/A |
| Abstract : | We present and analyze two simple algorithms for finding satisfying assignments of k-CNFs (Boolean formulae in conjunctive normal form with at most k literals per clause). The first is a randomized algorithm which, with probability approaching 1, finds a satisfying assignment of a satisfiable k-CNF formula F in time O(n, |