Class Description

PNP: P With Oracle Access To NP

See Δ2P.

Linked From

FP: Function Polynomial-Time

Sometimes defined as the class of functions computable in polynomial time by a Turing machine. (Generalizes P, which is defined in terms of decision problems only.)

However, if we want to compare FP to FNP, we should instead define it as the class of FNP problems (that is, polynomial-time predicates P(x,y)) for which there exists a polynomial-time algorithm that, given x, outputs any y such that P(x,y). That is, there could be more than one valid output, even though any given algorithm only returns one of them.

FP = FNP if and only if P = NP.

If FPNP = FPNP[log] (that is, allowed only a logarithmic number of queries), then P = NP [Kre88]. The corresponding result for PNP versus PNP[log] is not known, and indeed fails relative to some oracles (see [Har87b]).

More about...


MIPEXP: Exponential-Time Multi-Prover Interactive Proof

The exponential-time analogue of MIP.

In the unrelativized world, equals NEEXP.

There exists an oracle relative to which MIPEXP equals the intersection of P/poly, PNP, and ⊕P [BFT98].

More about...


PNPcc: Communication Complexity PNP

Not contained in PPcc [BVW07].

Does not contain BPPcc if partial functions are allowed [PPS14].

Contained in UPostBPPcc.

More about...