Given P=!NP

Is there a polynomial time TM such that for an input of formula and a satisfying assignment will yield a different satisfying assignmentif such exist?

  • $\begingroup$ Well, I think it's NPC problem, since it's possible that formula has only 1 assignment and you need to check if it's the case. I think, NTM could do that. $\endgroup$ – rus9384 Jun 9 '17 at 11:12
  • 1
    $\begingroup$ @rus9384, it is indeed NPC but that has nothing to do with the fact that "NTM could do that". This only shows the problem to be in NP. If you want to prove NP-completeness, you have to show that some NP-complete problem reduces to it. $\endgroup$ – holf Jun 9 '17 at 11:39
  • 1
    $\begingroup$ @holf I think your comment contains more errors, actually. It's certainly relevant whether or not the problem can be solved by an NTM: if it cannot, it is uncomputable so certainly isn't in NP. To be in NP, the problem must be solvable by an NTM in a polynomial number of steps. $\endgroup$ – David Richerby Jun 9 '17 at 20:23
  • 1
    $\begingroup$ @DavidRicherby you are of course right. Bad phrasing, should be more careful on this. $\endgroup$ – holf Jun 12 '17 at 9:38

Your problem is NP-complete. Let's call it NextSAT$(F,\tau)$: accept iff $\tau$ is a satisfying assignment of $F$ and there exists a satisfying assignment of $F$ different from $\tau$.

NextSAT is clearly in NP. We now show that SAT $\leq$ NextSAT.

Let $F$ be a CNF on variables $X = \{x_1,\ldots,x_n\}$. If $F$ is the empty CNF, it is obviously satisfiable and we can thus pick any satisfiable instance of NextSAT for the reduction.

Assume now that $F$ has at least one clause. Choose $\tau : X \rightarrow \{0,1\}$ that does not satisfy $F$. It is easy to find by simply choosing a clause of $F$ and negating all its literals. Let $$G = F \lor (\bigwedge_{i \leq n} \ell_i) = \bigwedge_{C \in F} \bigwedge_{i \leq n} C \lor \ell_i$$ where $\ell_i = x_i$ if $\tau(x_i) = 1$ and $\ell_i = \neg x_i$ otherwise. We see that $G$ can be written as a CNF of size polynomial in the size of $F$.

Now, clearly, the satisfying assignments of $G$ is the disjoint union of the satisfying assignments of $F$ and $\tau$ since $\tau$ is the only satisfying assignment of $\bigwedge_{i\leq n} \ell_i$ and does not satisfy $F$. Thus, $F$ is satisfiable if and only if there exists a satisfying assignment of $G$ different from $\tau$. That is, if and only if NextSAT$(G,\tau)$ returns $1$.

| cite | improve this answer | |
  • $\begingroup$ Thanks holf. What if F's only satisfying assignment is x=1 for all i? the reduction doesn't fail detecting it ? $\endgroup$ – bejamin65 Jun 9 '17 at 13:33
  • $\begingroup$ @bejamin65 You are right, there is a small bug. I'll fix my answer. $\endgroup$ – holf Jun 9 '17 at 16:22
  • $\begingroup$ Finding a non satisfying assignment if one exist can't be easy, otherwise tautology is decidable in polynomial time and $\mathsf{coNP=P}$. To fix this issue you can simply check if the all $1$ assignment is satisfying. If it isn't, you're good and can proceed as before, otherwise you have found a satisfying assignment, so $\varphi\in SAT$ and you can output some constant word in NextSAT. $\endgroup$ – Ariel Jun 10 '17 at 11:41
  • 1
    $\begingroup$ @Ariel: finding a non-satisfying assignment of a CNF is actually quite easy as you only have to negate a clause. E.g. $F = (x \lor y \lor z) \land F'$ is not satisfied by any $\tau$ such that $\tau(x)=\tau(y)=\tau(z)$. For this reasons, the coNP-complete version of TAUTOLOGY is usually defined with DNF as inputs (or general Boolean formulas). But I agree that your reduction works too when the 1-assignment satisfies $F$ and is easier than mine. $\endgroup$ – holf Jun 12 '17 at 9:47

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.