3
$\begingroup$

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 ?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Browsing wikipedia some more, I have a guess as to what it might mean. Is it a nondeterministic Turing machine which accepts its input only if every path returns "accept"? (as opposed to a standard NTM which accepts its input if there exists a path which returns "accept") $\endgroup$ – dspyz Jun 5 '13 at 8:46
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ How do you measure the running time of a program on such a machine? (to determine whether it's polynomial) I'd guess it's the number of steps taken along the longest path. Is this correct? $\endgroup$ – dspyz Jun 5 '13 at 8:52
  • $\begingroup$ The problem with oracle classes was one reason for me to ask: cs.stackexchange.com/q/10317/6716 $\endgroup$ – frafl Jun 5 '13 at 8:52
  • $\begingroup$ @dspyz: Yes, the same way as for "normal" NTMs. $\endgroup$ – frafl Jun 5 '13 at 8:54
  • 1
    $\begingroup$ I'm going to go ahead and clarify this on the Wikipedia page. $\endgroup$ – dspyz Jun 5 '13 at 8:56
  • $\begingroup$ I don't have enough CS Theory vocabulary to feel I can edit wikipedia clearly and correctly. Where can I find a proper definition of what $A^B$ actually means? $\endgroup$ – dspyz Jun 5 '13 at 9:18
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This doesn't clarify what it means to augment a Turing Machine in class co-NP with an oracle of some sort $\endgroup$ – dspyz Jun 5 '13 at 8:41
  • $\begingroup$ @dspyz: Equipping a verifier with an oracle works in the same way as equipping any other Turing machine and as I outlined in my answer there is no one definite "co-NP Turing machine" as co-NP can be defined in various ways which are compatible with oracles. $\endgroup$ – frafl Jun 5 '13 at 9:07
  • $\begingroup$ I think there's something I'm misunderstanding. A non-deterministic Turing Machine is a machine which accepts its input if there exists a path which returns "accept". Such a machine cannot be made to correctly solve problems in coNP in poly-time without somehow flipping the machine's output after it has finished running. Since this is not an operation allowable by a standard NTM, the "class of nondeterministic Turing Machines which quickly (in polynomial time) determine that their input satisfies co-NP" contains zero instances. $\endgroup$ – dspyz Jun 5 '13 at 9:23
  • $\begingroup$ If I tried to answer this properly, the comment would be longer than both answers combined. Consider asking a question about machine models or ways to define complexity classes. $\endgroup$ – frafl Jun 5 '13 at 9:48
  • $\begingroup$ @dspyz just to respond to the first comment (as frafl has done the rest), your question doesn't actually ask what it means to augment a TM - you as what a TM in P/NP/co-NP is (particularly co-NP). Perhaps you could edit the question to ask what you wanted, or better yet (seeing as you have accepted frafl's answer), ask another question! (I think "what does $A^{B}$ mean?" is a great question for cs.SE, as long as it hasn't already been asked). $\endgroup$ – Luke Mathieson Jun 5 '13 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.