Access Restriction

Author Savick'Y. Jir'I.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Dnf Tautology ♦ Limited Number ♦ Conjunctive Normal Form ♦ Positive Answer ♦ Following Consequence ♦ Result Implies ♦ Omega Gammaa ♦ Ff Occurrence
Abstract It is known that every DNF tautology with all monomials of length k contains a variable with at least\Omega\Gammaa k =k) occurrences. It is not known, however, if this bound is tight, i.e. if there are tautologies with at most O(2 k =k) occurrences of every variable. DNF tautologies with 2 k monomials of length k and with at most 2 k =k ff occurrences of every variable, where ff = log 3 4 \Gamma 1 0:26 are presented. This has the following consequence. Let (k; s)-SAT be k-SAT restricted to instances 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 NPcomplete and (k; s k \Gamma 1)-SAT is trivial in the sense that every instance has positive answer. The above result implies that s k 2 k =k ff . This improves the previously known bound s k 11 32 2 k . 1 Introduction Let a (k; s)-formula be a formula in conjunctive normal form whose clauses consist of exactly k literals and such that every variable ...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2000-01-01