Loading...
Please wait, while we are loading the content...
Similar Documents
The Local Lemma is asymptotically tight for SAT
| Content Provider | CiteSeerX |
|---|---|
| Author | Tardos, G. Szabo, T. Gebauer, H. |
| Abstract | The Local Lemma is a fundamental tool of probabilistic combinatorics and theoretical computer science, yet there are hardly any natural problems known where it provides an asymptotically tight answer. The main theme of our paper is to identify several of these problems, among them a couple of widely studied extremal functions related to certain restricted versions of the k-SAT problem, where the Local Lemma does give essentially optimal answers. As our main contribution, we construct unsatisfiable k-CNF formulas where every clause has k distinct literals and every variable appears in at most( |
| File Format | |
| Access Restriction | Open |
| Content Type | Text |
