# Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$

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$$

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.

• Thanks, I'm trying to understand your answer. Feb 21, 2021 at 21:21
• 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})$. Feb 21, 2021 at 21:24
• Thanks, I think I got it Feb 21, 2021 at 21:58
• 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? Feb 21, 2021 at 22:23
• Yes, because on a deterministic TM, you can't have multiple choices in a given configuration. Feb 21, 2021 at 23:02