Class Description

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

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

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