Number of the records: 1

DNF Tautologies with a Limited Number of Occurrences of Every Variable

SYSNO ASEP	0403463
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	DNF Tautologies with a Limited Number of Occurrences of Every Variable
Author(s)	Savický, Petr (UIVT-O)_{SAI, RID, ORCID} Sgall, Jiří (MU-W)_{RID, ORCID, SAI}
Source Title	Theoretical Computer Science. - : Elsevier - ISSN 0304-3975 Roč. 238, 1-2 (2000), s. 495-498
Number of pages	4 s.
Language	eng - English
Country	DE - Germany
Keywords	disjunctive normal form ; tautology ; occurences of variable
Subject RIV	BA - General Mathematics
R&D Projects	GA201/98/0717 GA ČR - Czech Science Foundation (CSF)
	IAA1019602 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
	GA201/97/P038 GA ČR - Czech Science Foundation (CSF)
	ME 103 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
CEZ	1030915
UT WOS	000087413600019
EID SCOPUS	0346639545
DOI	10.1016/S0304-3975(00)00036-0
Annotation	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
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2003

Number of the records: 1