Tovey's paper from 1982 clearly states that:

Theorem 2.1. Boolean satisfiability is NP-complete when restricted to instances with 2 or 3 variables per clause and at most 3 occurrences per variable.

Throughout the paper, he refers to a r,s-SAT formula as such:

Let r,s-SAT denote the class of instances with exactly r variables per clause and at most s occurrences per variable.

So by 3, 3-SAT, following the author's logic, I understand an instance that has exactly 3 variables per clause and variables appear at most 3 times in the entire given formula.

Furthermore, Tovey says that 3, 3-SAT is in fact trivial, and that

Theorem 2.4. Every instance of r,r-SAT is satisfiable

So obviously 3, 3-SAT is no exception to his Theorem 2.4.

What I don't understand though, if it was established in Theorem 2.1 that a boolean CNF expression made up of clauses with 2 or 3 variables is NP-complete, then why by say if there is a generalized clause with 2 variables present like:

A or B using his transformation or polynomial reduction used in proving Theorem 2.1 a clause with 2 literals could look like this: not(xi) or xi+1

I will refer to an instance formula of Theorem 2.1 as F from now on.

Why can't we create a new formula F' (from F) so that whenever we encounter such a clause like the one above:

  1. Remove the 2 literal clause cj, say cj = A or B
  2. Add for each clause cj removed a dummy variable, say dj in the new 2 clauses:
    • A or B or dj
    • A or B or not(dj)

And the resulting F' boolean formula is obviously 3, 3-SAT. Yet, from the transformation above it is obvious by rules of inference (A or B must be True as well if (A or B or dj) and (A or B or not(dj)) are True).

So, to me it seems that F is True whenever F' is True (and vice versa).

Therefore, the polynomial time reduction presented above would appear to be valid.

It resulted that any F formula that is Theorem 2.1 compliant (the problem being NP-complete) could be reduced to F', which is an instance of 3,3-SAT.

So why then 3,3-SAT isn't NP-complete?


1 Answer 1


And the resulting F' boolean formula is obviously 3, 3-SAT.

This is not true: by duplicating the literals $A$ and $B$, you may have too many occurences of some variable. E.g. your translation of

$$(x\vee y)\wedge (x\vee y\vee u)\wedge (x\vee y\vee v)$$ would yield $$(x\vee y\vee a)\wedge (x\vee y\vee\neg a)\wedge (x\vee y\vee u)\wedge (x\vee y\vee v),$$ but that has too many $x$s and $y$s.

  • 1
    $\begingroup$ Thanks! I didn't realize the pair of variables x, y could each appear 4 times but that makes sense. I wonder if the polynomial reduction would be valid for 3, 4-SAT though (3, 4-SAT is known to be NP-complete) $\endgroup$ Commented Jul 10 at 15:00
  • $\begingroup$ @nonsensicalworld Nope - consider e.g. $(x\vee y_1)\wedge (x\vee y_2)\wedge (x\vee y_3)\wedge [stuff]$. The reduction only works to 3,6-SAT since in general the number of occurrences of each variable can double. $\endgroup$ Commented Jul 11 at 17:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.