NP-complete Proof: 3-SAT is Polynomially Transformable

[mathmari]

Hey!

The proof that $3-$satisfiability is NP-complete, is the following:

We shall show that satisfiability for CNF (conjunctive normal form) expressions is polynomially transformable to $3-$satisfiability. Given a product of sums, replace each sum $(x_1+x_2+ \dots +x_k), k \geq 4$, with $$(x_1+x_2+y_1)(x_3+\overline{y}_1, y_2)(x_4+\overline{y}_2+y_3) \dots (x_{k-2}+\overline{y}_{k-4}+y_{k-3})(x_{k-1}+x_k+\overline{y}_{y-3}) \ \ \ \ \ (*)$$
for new variables $y_1, y_2, \dots, y_{k-3}$.

For example, for $k=4$, expression $(*)$ is $(x_1+x_2+y_1)(x_3+x_4 \overline{y}_1)$.

There is some assignment to the new variables which makes the replacing expression have value $1$ if and only if one of the literals $x_1, x_2, \dots , x_k$ has value $1$, that is, if and only if the original expression has value $1$. Assume $x_j=1$. Then set $y_j$ to $1$ for $j \leq i-2$ and set $y_j$ to $0$ for $j>i-2$. The replacing expression has value $1$. Conversely, assume that some assignment for the $y_i$'s makes the resulting expression have value $1$, If $y_1=0$, then either $x_1$ or$x_2$ must have value $1$. If $y_{k-3}=1$ then either $x_{k-1}$ or $x_{k}$ must have value $1$. If $y_1=1$ and $y_{k-3}=0$, then for some $i$, $1 \leq i \leq k-4$, $y_i=1$ and $y_{i+1}=0$, implying $x_{i+2}$ must have value $1$. In any event some $x_i$ must have value $1$.
The length of each replacing expression is bounded by a constant multiple of the length of the eplaced expression. In fact, given any CNF expression $E$, we can find, by applying the above transformations to each sum, a $3-$CNF expression $E'$ which is satisfiable if and only if the original expressiom is satisfiable. Moreover, we can find $E'$ in time proportional to the length of $E$, since the treansformations are straightforward to apply. Could you explain me this proof?? (Wondering)

 

[Evgeny.Makarov]

Given a product of sums, replace each sum $(x_1+x_2+ \dots +x_k), k \geq 4$, with $$(x_1+x_2+y_1)(x_3+\overline{y}_1, y_2)(x_4+\overline{y}_2+y_3) \dots (x_{k-2}+\overline{y}_{k-4}+y_{k-3})(x_{k-1}+x_k+\overline{y}_{y-3}) \ \ \ \ \ (*)$$
for new variables $y_1, y_2, \dots, y_{k-3}$.

The comma in the second factor should be a plus.

For example, for $k=4$, expression $(*)$ is $(x_1+x_2+y_1)(x_3+x_4 \overline{y}_1)$.

The expression should be $(x_1+x_2+y_1)(x_3+x_4 + \overline{y}_1)$.

Could you explain me this proof?

Explaining a proof is NP-hard. (Smile) For a single sentence or claim there is only a limited number of difficulties or ways it can be misunderstood, and all of them can be addressed in a short explanation. In a long proof, each claim has its potential difficulties, and difficulties from different parts of the proof may combine to create new once. Therefore, the number of potential things to explain is exponential in the size of the proof. So you'll have to point out individual sentences and describe what you don't understand about them if you want help...

 

[mathmari]

The comma in the second factor should be a plus.

The expression should be $(x_1+x_2+y_1)(x_3+x_4 + \overline{y}_1)$.

Yes, you're right! (Blush)

Explaining a proof is NP-hard. (Smile)

(Smile)

So you'll have to point out sentences and describe what you don't understand about them if you want help...

My questions are the following:

Given a product of sums, replace each sum $(x_1+x_2+ \dots +x_k), k \geq 4$, with $$(x_1+x_2+y_1)(x_3+\overline{y}_1 + y_2)(x_4+\overline{y}_2+y_3) \dots (x_{k-2}+\overline{y}_{k-4}+y_{k-3})(x_{k-1}+x_k+\overline{y}_{y-3}) \ \ \ \ \ (*)$$
for new variables $y_1, y_2, \dots, y_{k-3}$.

Why do we replace each sum with this expression?? (Wondering)

What do the new variables $y_i$ stand for?? (Wondering)

There is some assignment to the new variables which makes the replacing expression have value $1$ if and only if one of the literals $x_1, x_2, \dots , x_k$ has value $1$, that is, if and only if the original expression has value $1$.

Does this stand because it stands that $$\text{ TRUE OR FALSE = TRUE }$$ ?? (Wondering)

Assume $x_i=1$. Then set $y_j$ to $1$ for $j \leq i-2$ and set $y_j$ to $0$ for $j>i-2$. The replacing expression has value $1$.

Why do we set these values for $y_j$ ?? (Wondering)

Conversely, assume that some assignment for the $y_i$'s makes the resulting expression have value $1$, If $y_1=0$, then either $x_1$ or$x_2$ must have value $1$. If $y_{k-3}=1$ then either $x_{k-1}$ or $x_{k}$ must have value $1$. If $y_1=1$ and $y_{k-3}=0$, then for some $i$, $1 \leq i \leq k-4$, $y_i=1$ and $y_{i+1}=0$, implying $x_{i+2}$ must have value $1$. In any event some $x_i$ must have value $1$.

Could you explain to me why this stand?? (Wondering)

The length of each replacing expression is bounded by a constant multiple of the length of the replaced expression.

Why does this stand?? (Wondering)

Moreover, we can find $E'$ in time proportional to the length of $E$, since the transformations are straightforward to apply.

What does this mean?? (Wondering)

 

[Evgeny.Makarov]

First of all, let's say it explicitly that $+$ here denotes disjunction (not "exclusive or") and juxtaposition (writing formulas next to each other with no operation in between) denotes conjunction.

Why do we replace each sum with this expression?

We want to reduce the SATISFIABILITY problem to 3-SATISFIABILITY, which is its special case. The reduction in the other direction is trivial precisely because it is a special case. The required direction means that we have to reduce a more general problem to a more specific one. It's like trying to get an answer to a general question by asking questions that can be answered only with "Yes" and "No". So in the end we have to have an instance of 3-SAT, i.e., all clauses must have 3 literals.

What do the new variables $y_i$ stand for?

Intuitively, $y_i=x_{i+2}+\dots+x_k$. Note that $\bar{y}_i+x_{i+1}+y_{i+1}=y_i\to(x_{i+1}+y_{i+1})$.

There is some assignment to the new variables which makes the replacing expression have value $1$ if and only if one of the literals $x_1, x_2, \dots , x_k$ has value $1$, that is, if and only if the original expression has value $1$.

Does this stand because it stands that $$\text{ TRUE OR FALSE = TRUE }$$ ?

This is the claim that is only stated here. It is proved in the remainder of the argument.

If you still have questions, I'll try to answer them tomorrow.

 

[LudusRex]

Sure! This proof is showing that the problem of satisfiability for CNF expressions can be transformed into the problem of satisfiability for $3-$CNF expressions in polynomial time. This is important because it means that if we can efficiently solve the $3-$CNF problem, we can also efficiently solve the CNF problem.

The proof does this by showing that for any CNF expression, we can find a $3-$CNF expression that is satisfiable if and only if the original expression is satisfiable. This is done by replacing each sum of variables in the CNF expression with a specific $3-$CNF expression, as shown in the example for $k=4$. This replacement process can be done in polynomial time, since the length of the new expression is bounded by a constant multiple of the length of the original expression.

Additionally, the proof shows that if we have a satisfying assignment for the original expression, we can find a corresponding satisfying assignment for the $3-$CNF expression, and vice versa. This means that the two problems are equivalent and can be solved using the same algorithm.

Overall, this proof is important because it shows that the problem of satisfiability for CNF expressions is at least as difficult as the $3-$CNF problem, which is known to be NP-complete. This means that the CNF problem is also NP-complete, and helps us understand the complexity of this problem in the context of other problems in computer science.