DNF Tautologies with a Limited Number of Occurrences of Every Variable

0403463 - UIVT-O 20020001 RIV DE eng J - Journal Article
Savický, Petr - Sgall, Jiří
DNF Tautologies with a Limited Number of Occurrences of Every Variable.
Theoretical Computer Science. Roč. 238, 1-2 (2000), s. 495-498. ISSN 0304-3975. E-ISSN 1879-2294
R&D Projects: GA ČR GA201/98/0717; GA AV ČR IAA1019602; GA ČR GA201/97/P038; GA MŠMT ME 103
Institutional research plan: AV0Z1030915
Keywords : disjunctive normal form * tautology * occurences of variable
Subject RIV: BA - General Mathematics
Impact factor: 0.417, year: 2000

Let (k,s)-SAT be k-SAT restricted to formulas with at most s occurrences of every variable. It is known that for every k, there is an s_k such that (k,s_k)-SAT is NP-complete and (k,s_k-1)-SAT is trivial in the sense that all its instances have positive answer. In the paper, the best previously known upper bound s_k le 13/64*2
Permanent Link: http://hdl.handle.net/11104/0123768