# What does $A^B$ mean?

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.

• 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. – Ran G. Jun 6 '13 at 4:19

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.
• 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. – frafl Jun 6 '13 at 13:45
{"ft_lang_label":"__label__en","ft_lang_prob":0.9588133,"math_prob":0.9885261,"size":529,"snap":"2019-51-2020-05","text_gpt3_token_len":124,"char_repetition_ratio":0.1447619,"word_repetition_ratio":0.021052632,"special_character_ratio":0.2173913,"punctuation_ratio":0.056074765,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9994424,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-12-06T09:15:55Z\",\"WARC-Record-ID\":\"<urn:uuid:8d794846-695b-4d8b-bea3-eb3c8bd6ccaa>\",\"Content-Length\":\"135313\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6fee7df6-b372-499b-9499-a4d0b1941da4>\",\"WARC-Concurrent-To\":\"<urn:uuid:df442cb0-84cb-493b-800a-b528a3a12bf6>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/12480/what-does-ab-mean\",\"WARC-Payload-Digest\":\"sha1:SPLAA7Y3T4GWHXPNXHGOBSL4CJE7MJK3\",\"WARC-Block-Digest\":\"sha1:XAPCWDONZ3Z7NWWBPXNF6RMOTYLHU4WZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-51/CC-MAIN-2019-51_segments_1575540486979.4_warc_CC-MAIN-20191206073120-20191206101120-00033.warc.gz\"}"}