Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine M' that accepts whenever M rejects and rejects whenever M accepts? Why doesn't NP equal co-NP?
Thanks!
Best Answer
That works for deterministic machines, but not for nondeterministic, since a nondeterministic machine has many "branches" in its calculation, and a language is defined to be accepted by a machine if there exists a branch that accepts it (in the normal sense, that $q_{acc}$ is reached) and rejected if all branches reject. If the machine accepted a language by reaching an accept condition on some branches and rejecting on others, flipping the conditions you end up with a machine which again accepts that language, while you intended to make a machine that rejects it.