1 .5 basic concepts in theoretical computer science 19 C , we denote by C C the set of all problems that can be solved by an algorithm for C equipped with C -oracles, where a C -oracle solves a problem in C (or in coC ) in unit time. The class P 2 , defined as P NP , is thus the class of all decision problems that can be solved in polynomial time with the help of NP-oracles, which answer in unit time whether a given instance of a problem in NP is positive or not. The class P 2 is the subset of P 2 consisting of all decision problems that can be solved in polynomial time using “logarithmically many” NP-oracles. Equivalently, P 2 may be defined as the subset of P 2 for which a polynomial number of NP-oracles may be used, but these need to be queried in parallel, that is, we cannot use the answer to one oracle to determine what question to put to the next oracle. Finally, P 2 = NP NP and P 2 = co NP 2 . Thus, for instance, P 2 is the class of decision problems for which the correctness of a positive solution can be verified in polynomial time by an algorithm that has access to an NP-oracle. The following inclusions hold: P ⊆ NP, coNP ⊆ P 2 ⊆ P 2 ⊆ P 2 , P 2 . It is strongly believed that all these inclusions are strict, although none of them was actually proven to be strict. Interestingly, P 2 and (to a lesser extent) P 2 , P 2 and P 2 play an important role in computational social choice (and indeed, we find them referred to in Chapters 3, 4, 5, 8, 12, and 17). We occasionally refer to other complexity classes (such as PLS or #P) in the book; they are introduced in the chapter concerned. For a full introduction and an extensive overview of computational complexity theory, we refer the reader to Papadimitriou (1994) and Ausiello et al. (1999).