# Is 3, 3 satisfiability trivial after all?

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?

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.
• @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. Commented Jul 11 at 17:36