Počet záznamů: 1
DNF Tautologies with a Limited Number of Occurrences of Every Variable
- 1.
SYSNO ASEP 0403463 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název DNF Tautologies with a Limited Number of Occurrences of Every Variable Tvůrce(i) Savický, Petr (UIVT-O) SAI, RID, ORCID
Sgall, Jiří (MU-W) RID, ORCID, SAIZdroj.dok. Theoretical Computer Science. - : Elsevier - ISSN 0304-3975
Roč. 238, 1-2 (2000), s. 495-498Poč.str. 4 s. Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova disjunctive normal form ; tautology ; occurences of variable Vědní obor RIV BA - Obecná matematika CEP GA201/98/0717 GA ČR - Grantová agentura ČR IAA1019602 GA AV ČR - Akademie věd GA201/97/P038 GA ČR - Grantová agentura ČR ME 103 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ 1030915 UT WOS 000087413600019 EID SCOPUS 0346639545 DOI 10.1016/S0304-3975(00)00036-0 Anotace 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 Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2003
Počet záznamů: 1