The Size of SPP

John M. Hitchcock

Derandomization techniques are used to show that at least one of the following holds regarding the size of the counting complexity class SPP.

  1. SPP has p-measure 0.
  2. PH is contained in SPP.
In other words, SPP is small by being a negligible subset of exponential time or large by containing the entire polynomial-time hierarchy. This addresses an open problem about the complexity of the graph isomorphism problem: it is not weakly complete for exponential time unless PH is contained in SPP. It is also shown that the polynomial-time hierarchy is contained in SPPNP if NP does not have p-measure 0.