What is a Turing Machine in class coNP

Question

On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy

it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B"

What is a "Turing machine in class A" for classes P, NP, and coNP?

I'm guessing a Turing machine in P is a deterministic Turing machine that can only run for polynomial time in the size of its input

and that a Turing machine in NP is a nondeterministic Turing machine that can only run for polynomial time in the size of its input

But I have no clue what is a Turing machine in class coNP ?

Answer 1

You can define co-NP as: $$\{L\mid \exists\text{polyn.time } \text{NTM }M: L=\{w\mid \text{all computations paths of }M(w) \text{ accept}\} \}$$ This directly corresponds to the definition of the $\forall^p$ operator in the next section of the mentioned article. However, nearly all definitions of NP rely on TMs or some other concept of algorithms which usually can be equipped with oracles.

However you very well spotted a problem of the oracle definition for complexity classes: $\mathcal A^{\mathcal B}$ implicitly assumes that $\mathcal A$ can be defined using Turing machines, while it may be any set of languages. Sometimes this is avoided by defining $\mathcal A$ as a set of Turing machines or algorithms instead (usually denoted by the same name as the complexity class those algorithms define).

Answer 2

The easiest way (for me) to understand co-NP is as the class of problems where certificates for "No" answers can be quickly verified (i.e. certificates of non-membership).

So if we look at NP as a class of nondeterministic Turing Machines which quickly (in polynomial time) determine that their input satisfies some property $\Pi$, co-NP is the class of nondeterministic Turing Machines that quickly determine that their input does not satisfy $\Pi$ (or equivalently satisfies $\neg\Pi$).