Equals P with 2k-1 parallel queries to NP (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).
If PNP[1] = PNP[2], then PNP[1] = PNP[log] and indeed PH collapses to Δ3P (attributed in [Har87b] to J. Kadin).
Also known as Θ2P.
The class of decision problems solvable by a P machine, that can make O(log n) queries to an NP oracle (where n is the length of the input).
Equals P||NP, the class of decision problems solvable by a P machine that can make polynomially many nonadaptive queries to an NP oracle (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).
PNP[log] is contained in PP [BHW89].
Determining the winner in an election system proposed in 1876 by Charles Dodgson (a.k.a. Lewis Carroll) has been shown to be complete for PNP[log] [HHR97].
Contains PNP[k] for all constants k.