0
$\begingroup$

In Michael Sipser's book language is defined to be in NP iff it is decided by nondeterministic polynomial time Turnig machine. Why can't we use same machine to decide if language $L^c$ is in coNP? Just run every string x on same NDTM and if it accepts x then x is not in $L^c$ and if it rejects x then it is. What am I missing here?

In this book runnin time for NDTM is defind only for deciders, NDTM which halts in all branches.

$\endgroup$
  • $\begingroup$ You cannot compute NP with NDTMs that halt in all branches, I think. For these there is not even a real Halting Problem, because we know that they always halt. You only get the recursive functions. $\endgroup$ – Peter Leupold Jan 18 '17 at 11:23
  • $\begingroup$ I don't know what you are talking about. We decide "if a string $x$ is in a language $L^c$", not "if $L^c$ is in coNP". $\endgroup$ – aaaaajack Jan 18 '17 at 12:37
0
$\begingroup$

I assume that you want to "decide if $x\in L^c$ and output the complement". Tell me if I misunderstand.

$L^c$ is in NP if there's an NDTM accepts $x$ in "at least one" branch iff $x\in L^c$. So $x\in L$, i.e. $x\notin L^c$ means the NDTM rejects $x$ in "all" branches. Think more carefully about these quantifiers.

NDTM can always find the accepted branch if it exists, but this doesn't means the NDTM has checked all branches. So we can't decide if $x\in L$ with the same NDTM in the trivial way you mentioned.

Edit: If you want to prove $L\subseteq NP$, you should construct "one NDTM" such that there exists a polynomially long path to an accepting state iff $x\in L$. You might think flipping the answer is quite simple, but where's the answer? There doesn't even exist a state representing "NO". This is the problem. You can't add another Turing machine which read the output of $M$ and output its complement either since the whole structure is not a valid NDTM.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.