1
$\begingroup$

What's wrong with the following argument that $NP \subset coNP$?

let $L \in NP$; then there exists an NTM $N$ that decides $L$ in $f(n)$ time where $f(n) = O(n^k)$ for some natural number $k$.

Define $H = $ on input $z$:

  1. run $z$ on $N$ for at most $f(|z|)$ steps.
  2. if $N$ accepted, reject. If hasn't accepted, accept.

Then if $z \in \bar{L}$ then $N$ will not have accepted $z$ after any number of steps, so $z \in L(H)$.

If $z \in L(H)$ then $N$ hasn't accepted $z$ after $f(|z|)$ steps. If $z \in L$ then $N$ would have accepted it after $f(|z|)$ steps.

Is the problem here that computing $f(|z|)$ may not take polynomial time, in $|z|$? It seems like it should.

$\endgroup$
  • $\begingroup$ The problem is the second step, which you can't implement. Try rephrasing your argument using the witness definition of nondeterminism. $\endgroup$ – Yuval Filmus Jul 28 '18 at 10:59
  • $\begingroup$ @YuvalFilmus why can't step 2 be implemented? Can you elaborate please? $\endgroup$ – Mariah Jul 28 '18 at 14:19
0
$\begingroup$

This is not true:

Then if $z \in \bar{L}$ then $N$ will not have accepted $z$ after any number of steps, so $z \in L(H)$.

It might be $z \in \bar{L}$, but the machine will not be stopped anytime!

$\endgroup$

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