3
$\begingroup$

What does $A^B$ mean where A and B are complexity classes?

The "Polynomial Hierarchy" page 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

In that case what is a Turing machine in class A?

(besides just a machine of some sort that can solve problems in A, because that doesn't give any insight as to what it means to augment such a machine with an oracle)

The motivation for this question was: What is a Turing Machine in class coNP.

Improve this question
$\endgroup$
1
  • $\begingroup$ Yes, it's the augmentation of having oracle acess to some language in $B$. The TM is defined by $A$ (e.g, if $A=P$ the TM is deterministic, polynomially bounded; if $A=NP$, it is nondeterministic, polynomial). See the link to Wikipedia. $\endgroup$
    – Ran G.
    Jun 6, 2013 at 4:19

1 Answer 1

Reset to default
3
$\begingroup$

An oracle is a way for a Turing Machine to ask a question and get it answered immediately, "magically". The way we usually model it is that the Turing Machine can write down the question on a special, extra tape, and then (say) the tape is erased and the answer immediately written on it.

More specifically, we usually suppose that the oracle is for a particular language, so we write a string on the tape, followed by some special "end-of-string" symbol; then, the formula disappears and is replaced by either "YES" or "NO".

For a concrete example, suppose our Turing Machine has an oracle for SAT. Then it can write a formula on the string and immediately find out if it's satisfiable or not.

Notice that, since SAT is NP-Complete, a TM with a SAT oracle can decide any language in NP in polynomial time: Just reduce the input to a SAT formula, and then ask the oracle about this SAT formula.

So we might write $P^{NP}$ for the set of languages that can be decided in polynomial time by a TM with an oracle for SAT.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ The OP has more problems understanding the base class $\mathcal A$ than the concept of oracles, especially if it's not easy to figure out what a corresponding TM is. So probably some examples like $AC^{NP}$ or $(NP\cap co$-$NP)^{\mathcal C}$ would be nice. $\endgroup$
    – frafl
    Jun 6, 2013 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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