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