Class Description

ModP: ModkP With Arbitrary k

The class of decision problems solvable by a ModkP machine where k can vary depending on the input. The only requirement is that 0k be computable in polynomial time.

Defined in [KT96], where it was also shown that ModP is contained in AmpMP.

Linked From

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