Understanding definition of NP and co-NP

Question

From some of the texts I read, one definition of NP is: "An equivalent definition of NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." and that we have the following, where $n$ is the length of the input:

$$ \text{NP}=\bigcup \text{NTIME}(n^k) $$

This means that one way a problem can be shown to be $\in \text{NP}$ is if we can construct a non-deterministic TM $N$ using a polynomial time verifier $V$ on a certificate $C$, or:

TM $N$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$, accept

But if I use the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$, wouldn't this imply that $\text{co-NP} \subseteq \text{NP}$, since I can construct a TM $N'$ that can recognize co-NP:

TM $N'$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$ for any branch, reject
3. if all branches reject the guessed certificates, accept

In this case, since all branches of $N'$operate in polynomial time, $N'$ should also be able to solve problems for co-NP in non-deterministic polynomial time.

But since it is not yet sure if NP=co-NP, how should I understand the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$?

Answer 1

Nondeterministic machines are only allowed to behave nondeterministically in a limited way: very briefly, "Accept iff some branch has [property]" is permitted but "Accept iff no branch has [property]" is not. Unlike with deterministic machines, there's a fundamental element of asymmetry here. Your $N'$ is not, in fact, a nondeterministic Turing machine.

Rather, it's a "co-nondeterministic Turing machine" (if that were a term). Unsurprisingly, co-NP is exactly the set of languages accepted by some co-nondeterministic Turing machine, and the fact that NP=co-NP is open means exactly that it is not currently known whether nondeterministic and co-nondeterministic machines can compute the same things in polynomial time.