5
$\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: an assignment that has free variables. Example: $x_1 = 0, x_2 = \{0\ ,1\}, x_3 = 1$. Here $x_2$ value remains unassigned.

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$
3
  • $\begingroup$ Could you give one reference of "partial assignment" or is this one temporary definition for this question? By this article, "we can save the work of checking all extensions of the partial assignment. ... neither the truth assignment {p = 1, q = 0, r = 0} nor the assignment {p = 1, q = 0, r = 1} satisfies Δ" means partial assignment is something like {p = 1 , q = 0} when we have 3 variables able to be assigned values (i.e. partially assign some variables instead of all). It isn't related with "free variable". $\endgroup$
    – An5Drama
    Feb 13 at 2:48
  • 1
    $\begingroup$ I think that article agrees with my definition. I have removed "free variable" because, indeed, that made the description ambiguous. $\endgroup$
    – rus9384
    Feb 13 at 8:54
  • $\begingroup$ Not sure I understand the question correctly. Seems easy to prove the following: "At least one variable is true" easily translates into the CNF $x_1 \vee \dots \vee x_n$ but if you restrict to $k$-CNF with $k<n$, you can easily show that you need more than $n$ literals ($x_i$ needs to appears once. If you use extra encoding variables then this will have > n literals. Otherwise, one variable needs to appear at most twice (otherwise you have clauses with disjoint variables and you can quickly show that this will not be equivalent to what you need). $\endgroup$
    – holf
    Feb 14 at 7:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.