The closure of P under the ∃, ∀, and Modk operators. Equivalently, the smallest class C such that NPC, coNPC, and ModkPC are included in C for each k. Introduced in [GKR+95].
Contains PH and ModkP for each k. Contained in, and low for, AmpMP and MP.
For a fixed m, the restriction of the class that only allows Modk for k = m is denoted ModPHm [Buss17]. Toda’s theorem [Tod89] implies that for prime m, ModPHm = BP·ModmP.
The class of decision problems such that for some #P function f(x,0m),
Defined in [GKR+95].
Contains PH and ModPH. Contained in MP.
The class of decision problems such that for some #P function f, the answer on input x is 'yes' if and only if the middle bit of f(x) is 1.
Defined in [GKR+95].
Contains AmpMP, and ModPH, which is low for both AmpMP and MP. Contained in P#P[1].
MP with ModP oracle equals MP with #P oracle [KT96].
Contains PH [Tod89]. Indeed, contains MP, which in turn contains ModPH [GKR+95].