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

  • $\begingroup$ Thanks for the help, I fixed it, instead of block I meant bound / barrier $\endgroup$
    – dustyeav
    Jul 20 at 16:57
  • $\begingroup$ Do you allow clauses with less than $3$ literals to be in 3-SAT? $\endgroup$
    – Steven
    Jul 20 at 16:59
  • $\begingroup$ No, it should be in exactly clauses with 3 literals $\endgroup$
    – dustyeav
    Jul 20 at 17:01
  • $\begingroup$ Do you allow repeated literals? $\endgroup$
    – Steven
    Jul 20 at 17:01
  • $\begingroup$ Yes, Literal can appear several times in clauses. $\endgroup$
    – dustyeav
    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.
  • $\begingroup$ 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? $\endgroup$
    – dustyeav
    Jul 20 at 17:25
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Jul 20 at 17:29

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.