DNF tautologies with a limited number of occurrences of every variable
It is known that every DNF tautology with all monomials of length k contains a variable with at least Omega(2(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) occurences of every variable. DNF tautologies with 2(k) monomials of length ii and with at most 2(k)/k(alpha) occurrences of every variable, where alpha = log(3) 4-1 greater than or equal to 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 NP-complete and (k,s(k) - 1)-SAT is trivial in the sense that every instance has positive answer. The above result implies that s(k) less than or equal to 2(k)/k(alpha). This improves the previously known bound s(k) less than or equal to 13/64 2(k) for all k greater than or equal to 6. (C) 2000 Elsevier Science B.V. All rights reserved.
tautology disjunctive normal form occurrences of variable