__
TR03-063 | 2nd July 2003 00:00
__

#### The Size of SPP

**Abstract:**
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 SPP^NP if NP does not

have p-measure 0.