Class Description

P#P: P With #P Oracle

I decided this class is so important that it deserves an entry of its own, apart from #P.

Contains PH [Tod89], and is contained in CH and in PSPACE.

Equals PPP (exercise for the visitor).

Linked From

#P: Sharp-P or Number-P

The class of function problems of the form "compute f(x)," where f is the number of accepting paths of an NP machine.

The canonical #P-complete problem is #SAT.

Defined in [Val79], where it was also shown that #Perfect Matching (or equivalently, Permanent) is #P-complete. What makes that interesting is that the associated decision problem Perfect Matching is in P.

PH is in P#P [Tod89].

Any function in #P can be approximated to within a polynomial factor in BPP with NP oracle [Sto85]. Likewise, any problem in #P can be approximated to within a constant factor by a machine in FP||NP running in time [SU05].

More about...


D#P: Alternate Name for P#P

More about...


PPP: P With PP Oracle

A level of the counting hierarchy CH.

It is not known whether there exists an oracle relative to which PPP does not equal PSPACE.

Contains PPPH [Tod89].

Equals P#P (exercise for the visitor).

Since the permanent of a matrix is #P-complete [Val79], Toda's theorem implies that any problem in the polynomial hierarchy can be solved by computing a sequence of permanents.

More about...


PSPACE: Polynomial-Space

The class of decision problems solvable by a Turing machine in polynomial space.

Equals NPSPACE [Sav70], AP [CKS81], and CZK assuming the existence of one-way functions [BGG+90].

Equals IP [Sha90], but PSPACE strictly contains IP with probability 1 [CCG+94].

Contains P#P (P with a #P oracle).

A canonical PSPACE-complete problem is QBF.

Relative to a random oracle, PSPACE strictly contains PH with probability 1 [Cai86].

PSPACE has a complete problem that is both downward self-reducible and random self-reducible [TV02]. It is the largest class with such a complete problem.

Contained in EXP. There exists an oracle relative to which this containment is proper [Dek76].

In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, FO() which is also FO(PFP) and SO() which is also SO(TC).

More about...