The variable bound conjecture for minimally unsatisfiable kk-DNF sets

Let kk be a fixed positive integer, and let D{\mathbb{D}} be a minimally unsatisfiable set of kk-DNF formulas. Write D\lvert{\mathbb{D}}\rvert for the number of formulas in D{\mathbb{D}}. The number of variables occurring in D{\mathbb{D}} is at most

O(Dk).\mathrm{O}\bigl(\lvert{\mathbb{D}}\rvert^k\bigr).

Variable bound conjecture. Suppose that D{\mathbb{D}} is a minimally unsatisfiable kk-DNF set for some arbitrary but fixed positive integer kk. Then the number of variables in D{\mathbb{D}} is at most O(Dk)\mathrm{O}\bigl(\lvert{\mathbb{D}}\rvert^k\bigr). This conjecture would close the gap between the known lower bound Ω(mk)\Omega(m^k) and upper bound O((mk)k+1)\mathrm{O}((mk)^{k+1}) for the number of variables in a minimally unsatisfiable kk-DNF set with mm formulas; the exponent is expected to decrease from k+1k+1 to kk.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.