Consider the variant of the 3SAT problem with the following restrictions:
Each clause has 2 or 3 literals.
Each pair of 3-literal clauses have at most one common variable.
What is the complexity of this SAT problem?
$\begingroup$
$\endgroup$
-
1$\begingroup$ Okay. Property 3 seems to be a restatement of property 2 -- am I wrong in saying that? I'm also not sure is meant by "after some manipulation of the clauses." $\endgroup$ – gdmclellan Jun 30 '16 at 17:36
-
$\begingroup$ Q+N=1 P+Q+R=1 M+N+R=1 can also be written as: Q+N=1 P+Q+R=1 M+~Q+R=1 The first and second set of clauses are same but after the replacement, second set fails 2. Where as the first set seems to pass 2. Hence 3: Any such possible replacements also must not violatate 2. for any pair of clauses. (perhaps not very properly stated, but this is the idea). $\endgroup$ – TheoryQuest1 Jun 30 '16 at 17:44
-
1$\begingroup$ The two systems in your example don't appear to be equivalent. Take for example N = P = 1, all other vars 0. You should also probably clarify your what kinds of manipulations count as "some manipulation of the clauses" (e.g. can new variables and/or clauses be introduced?), and you should use a more commonplace notation (e.g. the clauses in your first system would be written $Q \vee N, P \vee Q \vee R, M \vee N \vee R$) unless you actually intend formulae that are composed of operations outside of the typical SAT connectives (e.g. if + is the exclusive-or operator). $\endgroup$ – gdmclellan Jun 30 '16 at 18:12
$\begingroup$
$\endgroup$
The central insight is that you can use two $2$-variable clauses to make sure two variables have the same value. Let me abbreviate $(x \vee \neg y) \wedge (y \vee \neg x)$ with $x=y$. This allows the following reduction from 3SAT.
Given a 3SAT formula, copy the clauses to your reduction one by one. If you encounter a clause with a variable $x$ you've already seen twice, write the clause with a new variable $y$ instead of $x$ and add two $2$-variable clauses for $x=y$. Call the resulting formula $\phi$.
Formula $\phi$ satisfies requirements 1) and 2). Next, employ the same technique to ensure requirement 3). Walk through each pair of $3$-variable clauses of $\phi$ and for each pair which shares two variables $x$ and $y$, keep $x$ in one clause and in the other clause, change $x$ to $z$, and add $x=z$. An example:
$(x\vee y\vee h) \wedge (\neg x \vee \neg y \vee h) \mapsto (x\vee y\vee h) \wedge (\neg x \vee \neg z \vee h) \wedge (y=z)$
The resulting formula has as many $3$-variable clauses as the original and two $2$-variable clauses for each third or later repetition of a variable and then some more to satisfy requirement 3). Because the $2$-variable clauses ensure that $x=y$ so that your substitutions work, the resulting formula is satisfiable exactly when the original 3SAT formula was satisfiable. Its length is at most quadratic in the number of clauses of the original formula, so your problem is NP-Complete.
EDIT: I notice I interpreted your question to mean, a variable cannot appear in more than two $3$-variable clauses. The way it is formulated now, requirements 2) and 3) are equivalent. I hope you're not mad.
answered Jul 1 '16 at 13:30
-
$\begingroup$ It is interesting to see that even when we demand the formula to be MONOTONE (ie, each clause is either +ve or -ve), the problem is NP-complete using basically the same trick (we will introduce $x\vee y$ and $\bar{x}\vee \bar{y}$ to make a copy of $x$) $\endgroup$ – Cyriac Antony Oct 18 '19 at 9:47
-
$\begingroup$ @CyriacAntony Good observation. That's interesting. $\endgroup$ – Lieuwe Vinkhuijzen Oct 18 '19 at 10:44
