The variable bound conjecture for minimally unsatisfiable -DNF sets
The variable bound conjecture for minimally unsatisfiable -DNF sets
Let be a fixed positive integer, and let be a minimally unsatisfiable set of -DNF formulas. Write for the number of formulas in . The number of variables occurring in is at most
Variable bound conjecture. Suppose that is a minimally unsatisfiable -DNF set for some arbitrary but fixed positive integer . Then the number of variables in is at most . This conjecture would close the gap between the known lower bound and upper bound for the number of variables in a minimally unsatisfiable -DNF set with formulas; the exponent is expected to decrease from to .
Sources & referencesView supporting material
Primary source
Jakob Nordström and Alexander Razborov, “On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution”, arXiv:0910.3127 (2009).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.