DNF Tautologies with a Limited Number of Occurrences of Every Variable

0403463 - UIVT-O 20020001 RIV DE eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GA201/98/0717; GA AV ČR IAA1019602; GA ČR GA201/97/P038; GA MŠMT ME 103
Výzkumný záměr: AV0Z1030915
Klíčová slova: disjunctive normal form * tautology * occurences of variable
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.417, rok: 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
Trvalý link: http://hdl.handle.net/11104/0123768