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

Citováno: 13

--- BERKE, R. - SZABO, T. Deciding relaxed two-colorability - A hardness jump. ALGORITHMS - ESA 2006, PROCEEDINGS. ISSN 0302-9743, 2006, vol. 4168, p. 124-135. [WOS]
--- GONG, P. - XU, D.Y. A new lower bound of critical function for (k,s)-SAT. THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS. ISSN 0302-9743, 2006, vol. 3959, p. 274-282. [WOS]
--- HOORY, S. - SZEIDER, S. A note on unsatisfiable k-CNF formulas with few occurrences per variable. SIAM JOURNAL ON DISCRETE MATHEMATICS. ISSN 0895-4801, 2006, vol. 20, no. 2, p. 523-528. [WOS]
--- HOORY, S. - SZEIDER, S. Computing unsatisfiable k-SAT instances with few occurrences per variable. THEORETICAL COMPUTER SCIENCE. ISSN 0304-3975, JUN 9 2005, vol. 337, no. 1-3, p. 347-359. [WOS]
--- SLOAN, R.H. - SZORENY, B. - TURAN, G. On k-term DNF with the largest number of prime implicants. SIAM JOURNAL ON DISCRETE MATHEMATICS. ISSN 0895-4801, 2007, vol. 21, no. 4, p. 987-998. [WOS]
--- GEBAUER, H. Disproof of the Neighborhood Conjecture with Implications to SAT. ALGORITHMS - ESA 2009, PROCEEDINGS. ISSN 0302-9743, 2009, vol. 5757, p. 764-775. [WOS]
--- GEBAUER, H. - SZABO, T. - TARDOS, G. The Local Lemma is Tight for SAT. PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS. 2011, p. 664-674. [WOS]
--- GEBAUER, H. Disproof of the neighborhood conjecture with implications to SAT. COMBINATORICA. ISSN 0209-9683, MAY 2012, vol. 32, no. 5, p. 573-587. [WOS]
--- SCHEDER, D. Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas. ALGORITHMS AND COMPUTATION. ISSN 0302-9743, 2013, vol. 8283, p. 251-261. [WOS]
--- SCHEDER, D. Unsatisfiable CNF Formulas contain Many Conflicts. ALGORITHMS AND COMPUTATION. ISSN 0302-9743, 2013, vol. 8283, p. 273-283. [WOS]
--- GEBAUER, H. - SZABO, T. - TARDOS, G. The Local Lemma Is Asymptotically Tight for SAT. JOURNAL OF THE ACM. ISSN 0004-5411, DEC 2016, vol. 63, no. 5. [WOS]
--- FU, Z.F. - XU, D.Y. Uniquely Satisfiabled-Regular (k,s)-SAT Instances. ENTROPY. MAY 2020, vol. 22, no. 5. [WOS]
--- FU, Z.F. - XU, D.Y. - WANG, Y.P. (1,0)-Super Solutions of (k,s)-CNF Formula. ENTROPY. FEB 2020, vol. 22, no. 2. [WOS]

Trvalý link: http://hdl.handle.net/11104/0123768