When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa. I'm thinking that this equal to $P=NP$, but I saw a solution (an example) that I disagree with: $M$ is a non-deterministic polynomial by time Turing machine that decide $SAT$, if all that paths are rejected then $L(\overline{M})=\Sigma^*\in P$

Is it a valid solution, or as I'm thinking $L(M)\in NPC$ and $L(\overline{M})\in P \Leftrightarrow P=NP$


1 Answer 1


Let's imagine a Non Deterministic Turing Machine $M$ that decide $SAT$. If we tune this machine a bit, and add a transition on the initial state, for every letter read, that reject the entry. Let $M'$ be the new NTM. Then, $L(M') = L(M)$, since $u\in L(M) \Leftrightarrow \exists$ at least one computational path in $M$ to an accepting state (and the same thing for $M'$).

Now consider $\overline{M'}$. Since we added a rejecting transition which is possible for every entry in $M'$, that means that there is an accepting transition for every entry in $\overline{M'}$, so it means that $L(\overline{M'}) = \Sigma^* \in P$.

That does not necessarily imply that $P = NP$, the reason being that $L(\overline{M'}) \neq \overline{L(M')}$.

Generaly speaking, $L \in NPC \Leftrightarrow \overline{L} \in \text{co-}NPC$, but that is not the case if you consider a Turing Machine and its switched version.

  • $\begingroup$ Thanks, I'm trying to understand your answer. $\endgroup$ Feb 21, 2021 at 21:21
  • $\begingroup$ The key is that to be accepted by a NTM, there must exists at least one accepting path. But if for an entry $u$ there exist both an accepting path and a rejecting path, then $u \in L(M)$ AND $u \in L(\overline{M})$. $\endgroup$
    – Nathaniel
    Feb 21, 2021 at 21:24
  • $\begingroup$ Thanks, I think I got it $\endgroup$ Feb 21, 2021 at 21:58
  • $\begingroup$ Is it possible to "add a transition on the initial state" without changing the accepting states only because it's Non Deterministic Turing Machine, or I missed something? $\endgroup$ Feb 21, 2021 at 22:23
  • 1
    $\begingroup$ Yes, because on a deterministic TM, you can't have multiple choices in a given configuration. $\endgroup$
    – Nathaniel
    Feb 21, 2021 at 23:02

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.