Input interpretation
P | P^PP (complexity classes)
Result
P^PP (superset equal) P
Best subsets
P^PP | P^PP (superset equal) P^#P[1] | P^PP (superset equal) P^QMA
P | P (superset equal) AL | P (superset equal) L | P (superset equal) LIN | P (superset equal) NC | P (superset equal) NL | P (superset equal) SC
Best supersets
P^PP | P^PP (subset equal) MP^#P
P | P (subset equal) AvgP | P (subset equal) beta_2P | P (subset equal) intersection _cobeta_2P | P (subset equal) intersection _cocompNP | P (subset equal) intersection _coHalfP | P (subset equal) intersection _coUP | P (subset equal) compNP | (6 more)
Time constraint
P^PP | (none)
P | !(*FormBox[
RowBox[{
RowBox[{“T”, “(“, “n”, “)”}], “=”,
RowBox[{
RowBox[{“O”, “(“, SuperscriptBox[“n”, “c”], “)”}], “=”, SuperscriptBox[“2”,
RowBox[{“O”, “(“,
RowBox[{“log”, ” “, “n”}], “)”}]]}]}],
TraditionalForm]) (on a deterministic Turing machine)
Known equalities
P^PP | (none)
P | P = AL
Canonical problems
P^PP | (none)
P | composite number | linear programming | marriage | graph reachability | 2 SAT | game of Nim | matrix multiplication | greatest common divisor | maximum matching | …
Conjectured equalities
P^PP | (none)
P | P = BPP
Class inclusions diagram
(supersets shown above subsets)