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