# What's wrong with the following argument that $NP \subset coNP$? [duplicate]

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.

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

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!