Class Description

ModPH: Modular Counting Hierarchy

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.

Linked From

AmpMP: Amplifiable MP

The class of decision problems such that for some #P function f(x,0m),

  1. The answer on input x is 'yes' if and only if the middle bit of f(x) is 1.
  2. The m bits of f(x) to the left and right of the middle bit are all 0.

Defined in [GKR+95].

Contains PH and ModPH. Contained in MP.

More about...


MP: Middle-Bit P

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].

More about...


P#P[1]: P With Single Query To #P Oracle

Contains PH [Tod89]. Indeed, contains MP, which in turn contains ModPH [GKR+95].

More about...