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: $${Lmid existstext{polyn.time } text{NTM }M: L={wmid 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
