4
$\begingroup$

Let $\Phi$ be a k-CNF and $\Phi_{min}$ be a minimal CNF (one that contains smallest amount of literal occurences) that is equal to $\Phi$.

Can $\Phi_{min}$ contain a clause of size $m > k$?

What I have tried:

Let's define the concept of partial assignment: asingnment that has free variables. Example: $x_1 = 0, x_2 = \{0\ ,1\}, x_3 = 1$. Here $x_2$ is a free variable.

If $\Phi$ contains clause $C(p)$, then $\Phi(\overline p) =0$.

Example: $\Phi = (x_1\lor x_2\lor x_3)\land (x_2\lor x_3\lor x_4)$. Here $\Phi(x_1=0,x_2=0,x_3=0)=0$.

  1. Going further, if $\Phi$ is k-CNF, it means that shortest unsatisfied partial assignment has length $l\leq k$.

  2. Also, formula already contains info about all unsatisfied partial assignments.

P.1 and p.2 says, that we don't need to use partial assignment of length $l>k$ to express the formula.

One more statement, $\Phi(p)=0\Rightarrow \Phi(p, x_i)=0$, where $x_i$ is fixed variable that is not in $p$.

Here is where I got stuck: $\Phi_{min}$ contains smallest amount of shortest inverted partial assignments of formula $\Phi$. Let's say that each of partial assignments $p_1, p_2$ has length $l$, such that $\Phi(p_1) =0, \Phi(p_2)=0$. Can we change them to one longer partial assignment $p$?

Restrictions are following: if you'll change or remove any variable in $p_1$ or $p_2$ (we'll call them $p'_1$ and $p'_2$ respectively), then $\Phi(p'_1) = 1$ and $\Phi(p'_2)=1$.

Intuitively it seems that they can't be combined, but what about logic?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.