[Solved]: What is a Turing Machine in class coNP

Problem Detail: 

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 ?

Asked By : dspyz

Answered By : frafl

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12466

 Ask a Question

 Download Related Notes/Documents