0
$\begingroup$

I can't find a mistake in reasoning : Let $M_1$ NTM (Non Deterministic Turing Machine) that solves $L$ in polynomial-time. So then $x \in L \Leftrightarrow M_1(x) = 1$. Finally our new NTM $M_2$ that solves $\bar{L}$ is inverted $M_1$ : $x \in \bar{L} \Leftrightarrow M_2(x) = 1 \Leftrightarrow M_1(x) = 0$. And since I have NTM $M_2$ that solves $\bar{L}$ then $\bar{L} \in NP \rightarrow coNP \subset NP$. And vice versa $NP \subset coNP$.

May you help me?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Rule of thumb: the "flip final states" construction only works for determinstic models. Study how it fails for NFA to understand why. See also here and here. $\endgroup$ – Raphael♦ Jan 31 '18 at 15:37
  • $\begingroup$ Thank you @David Richerby, now it is clear. If we want to prove that $\bar{L} \in NP$ we must show that in case $x \notin \bar{L} \Rightarrow \forall$ path in $G_{\bar{M}, x}$ - configuration graph we will come to a $C_{reject}$ configuration. (I emphasize $\textbf{for all}$ paths), but not inverted NTM $M$ in case $x \in L$ only gives the implication $\exists$ path $C_{start} \rightarrow C_{acc}$ that equals $x \notin \bar{L}$ for inverted NTM $\bar{M}$ $\exists$ path $C_{start} \rightarrow C_{rej}$ but unfortunately it is only $\exists$ not $\forall$. $\endgroup$ – Jason Gradlin Jan 31 '18 at 16:24