Why isn't NP=coNP?

84 Views Asked by At

My understanding is that if a problem is in NP, there is a nondeterministic polynomial-time Turing machine that decides it. That is to say, if an NP problem has a solution, the NP machine has a poly-length computational path on its computation tree (length < p(n) for some polynomial p, input length n)).

But doesn't that imply that NP = coNP? Because the definition of coNP is that there is an NP machine that decides if the problem's answer is false. We can design such an NP machine easily: run the first NP machine for p(n) steps, and if it hasn't accepted yet, output TRUE. But if a path accepts, output FALSE.