patternMinor
For complexity classes A and B, what does $A^B$ mean?
Viewed 0 times
whatmeanforclassesdoesandcomplexity
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#12480, answer score: 3
Revisions (0)
No revisions yet.