1
$\begingroup$

I have already defined here what is minimal 3CNF formula.

In the answer to the question, D.W. answered:

What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

In response to:

In a minimal k-cnf formula, there should be 2k different k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

So my question is now, what is the largest possible minimal 3CNF formula or how many clauses there are in the largest possible minimal 3CNF formula, i.e. what is the maximum number of clauses in the largest minimal 3CNF formula as function of n, where n is the number of variables in the 3CNF formula.

Is it $O(n)$? Is it $O(log(n))$? Is it $O(1)$, but just larger than 8?

$\endgroup$
  • 1
    $\begingroup$ It's at least $\Omega(n)$, considering $x_1 \land (\lnot x_1 \lor x_2) \land (\lnot x_2 \lor x_3) \land \cdots \land (\lnot x_{n-1} \lor x_n) \land \lnot x_n$. $\endgroup$ – Yuval Filmus Aug 2 '17 at 19:59
  • $\begingroup$ But this is 2CNF formula, I am talking about 3CNF formulas, not 2CNF. $\endgroup$ – Farewell Stack Exchange Aug 2 '17 at 20:08
3
$\begingroup$

Chungboom Lee, On the size of minimal unsatisfiable formulas shows that when $k=2$, the answer is $\Theta(n)$, and when $k \geq 3$, the answer is $\Theta(n^k)$. Here $k$ is width of the clauses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.