# Reduction from SAT to 3SAT

a few days ago I had a test and could not pass it. This is a question I did not understand in the test.

Recall the reduction we saw $$SAT \leq _p 3SAT$$. Given verse $$\varphi$$ in the form of $$CNF$$, we converted each fragment $$C_i$$ in $$\varphi$$ to verse $$D_i$$ in the form of $$CNF$$ by adding new variables. Then, we returned:

$$f(\varphi )= \wedge _{i=1}^{m}D_i$$, for m is the number of verses in $$\varphi$$.

Let there be some verse $$\varphi= C_1\wedge C_2 \wedge \cdots \wedge C_m$$.

Find a bound on the number of verses in $$f(\varphi)$$:

1. Between $$m$$ and $$m^2$$
2. Between $$2m$$ and $$m^2$$
3. If we denote by $$h$$ the amount of variables in the longest verse in $$\varphi$$ then: $$(h-2)\cdot m$$.
4. This cannot be determined because we do not know the size of each verse $$C_i$$
5. None of the above claims are true.

I can not find the answer. I can not find a relationship between m and h and the size of the number of verses

• Thanks for the help, I fixed it, instead of block I meant bound / barrier Jul 20 at 16:57
• Do you allow clauses with less than $3$ literals to be in 3-SAT? Jul 20 at 16:59
• No, it should be in exactly clauses with 3 literals Jul 20 at 17:01
• Do you allow repeated literals? Jul 20 at 17:01
• Yes, Literal can appear several times in clauses. Jul 20 at 17:03

This question refers to a specific transformation that you have seen during the course but we are not given, so we can only guess.

A standard transformation from a SAT clause $$C$$ to a collection of 3-SAT clauses is as follows:

• If $$C$$ already contains $$3$$ literals, then $$C$$ is left unchanged.
• If $$C$$ contains $$1$$ (resp. $$2$$) literals, then add $$2$$ (resp. $$1$$) copies of a literal from $$C$$ to $$C$$ itself.
• If $$C$$ contains $$k \ge 4$$ literals, then let $$C = \ell_1 \vee \ell_2 \vee \dots \vee \ell_k$$. Add $$k-3$$ new variables $$x_3, \dots, x_{k-1}$$ andeplace $$C$$ with: $$(\ell_1 \vee \ell_2 \vee x_3) \wedge \left( \bigwedge_{i=3}^{k-2}(\overline{x}_i \vee \ell_i \vee x_{i+1}) \right) \wedge (\overline{x}_{k-1}, \ell_{k-1}, \ell_k)$$

Notice how the above subformula contains 2 original literals in the first and in the last clauses, and 1 original literal in each of the intermediate clauses. Therefore the overall number of 3-SAT clauses needed to represent $$C$$ is $$2 + (k-4) = k-2$$.

This shows you that option 3 is correct.

Regarding the other options:

• 1 Is incorrect. Think of a formula with a single clause with $$4$$ variables.
• 2 Is incorrect. Think of a SAT formula that is also already a 3-SAT formula.
• Regarding 4, we can certainly find upper and lower bounds. In fact we can even find the exact number of clauses. If there are $$m$$ clauses and the number of variables in the $$i$$-th clause is $$m_i$$ then the final number of clauses will be $$\sum_{i=1}^m \max\{m_i-2, 1\}$$.
• 5 is false since 3 is true.
• If we have 9 clauses of 6 variables and one clause of a single variable. We'll need 31 clauses, while the option 3 suggests 30, am I right? Jul 20 at 17:25
• To transform each of the 9 clauses of 6 variables you need $4$ 3-SAT clauses, for a total of $9 \cdot 4 = 36$ clauses. We only need 1 3-SAT clause to encode the clause with a single variable. Overall we need $36+1 = 37$ clauses. Option 3 says we need [at most, i presume] $(h-2) \cdot 10 = (6-2) \cdot 10 = 4 \cdot 10 = 40$ clauses. Jul 20 at 17:29