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

This question already has an answer here:

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.

## marked as duplicate by Yuval Filmus complexity-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jul 28 '18 at 14:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 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

## 1 Answer

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!