3
$\begingroup$

Given a 3SAT problem where each clause is a Monotone Clause (i.e. each clause with all positive or negative literals).

Moreover, we are promised that each solution for the above SAT problem (if any exists at all) will be of the form 1 in 3 SAT.

Monotone 1 in 3 SAT is NP Complete, but with the additional promise above, does the problem still remain NP Complete (it obviously is NP) ?

$\endgroup$
  • $\begingroup$ What does it mean for a promise problem to be NP-complete? related $\endgroup$ – Ariel Feb 9 '18 at 17:33
  • $\begingroup$ The promise is that for any/each valid solution to the 3SAT instance would have a specific format: 'Exactly one literal would be true on assignment In each clause'. Eg: for any clause a+b+c=1 in 3SAT, the assignment would be one of the three (in any solution): a. (0, 0, 1) b. (0, 1, 0) c. (1, 0, 0). $\endgroup$ – J.Doe Feb 9 '18 at 17:44
  • $\begingroup$ The problem is that the definition of NP completeness only relates to decision problems. You only explained what the promise problem is, and not what you mean by saying that it is NP complete (or even in NP). $\endgroup$ – Ariel Feb 9 '18 at 17:49
  • $\begingroup$ I understand. Given the above promise (that the solution if it exists would be in a certain format described above). Now, if we are given a claimed solution; testing if its a valid 3SAT solution, that also satisfies the above property/promise for given solution; this can be done in polynomial time, so the problem is in NP. Now, finding one such solution itself, is that problem NP Complete ? $\endgroup$ – J.Doe Feb 9 '18 at 18:02
  • $\begingroup$ I suggest that you carefully go over the definitions. Being in NP has a very precise meaning. I understand that given an input in the promise, there are witnesses for being in the "yes" part inside that promise, but what about strings outside the promise? The definition of NP does not allow you to disregard strings because you are not interested in them. Also, finding a solution is a search problem, and is thus not in NP, which contains only decision problems. $\endgroup$ – Ariel Feb 9 '18 at 18:12
3
$\begingroup$

The trivial answer is no, as promise problems cannot be (by definition) in NP, and thus cannot be NP complete. The basic complexity classes e.g. $P, NP$ refer only to decision problems.

However, if you want to relate your promise problem to the standard classes, you can say it is NP-hard in the sense that if it can be solved in polynomial time for inputs in the promise, then $P=NP$.

To see why the above holds, let us introduce some notations. Let $C$ be the set of all monotone clause 3CNF, for which all satisfying assignments are 1 in 3. We shall call this set "the promise". Now your problem is, given an input in $C$, to determine whether it lies in $L_{yes}=C\cap SAT$, or in $L_{no}=C\setminus L_{yes}=C\cap\overline{SAT}$. Given an instance $\varphi$ to monotone clause 1 in 3 SAT, transform it to a monotone clause 3CNF $\psi$ such that $\psi\in C$, and in addition every 1 in 3 satisfying assignment for $\varphi$ also satisfies $\psi$. You can construct $\psi$ by adding clauses which negate conjunctions of pairs of literals in the same clause. Since $\psi\in C$ for every possible $\varphi$, and in addition $\varphi$ has a one in three satisfying assignment iff $\psi\in L_{yes}$, then solving the promise problem in polynomial time allows you to determine whether $\varphi$ has a one in three satisfying assignment, and thus $P=NP$.

The above basically shows that you can reduce an NP complete problem to your promise problem, but when talking about promise problems the definition of reduction should be slightly adjusted. Let us say that $f$ is a reduction from $L$ to the promise problem $L_{yes}\cup L_{no}$ if $Im(f)\subseteq L_{yes}\cup L_{no}$ and for every $x$ it holds that $x\in L\iff f(x)\in L_{yes}$. This is equivalent to saying that $x\in L\Rightarrow f(x)\in L_{yes}$ and $x\notin L\Rightarrow f(x)\in L_{no}$ (note that not being in $L_{yes}$ does not imply being in $L_{no}$).

$\endgroup$
  • $\begingroup$ Thanks. I still have to look at the exact construction, but I did get the line of argument. $\endgroup$ – J.Doe Feb 9 '18 at 18:44

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.