There is some language L computable in time 2First are the complexity class collapses. As always see the Zoo if some class does not look familiar.^{O(n)}such that for some ε>0, every algorithm A computing L uses 2^{εn}space for sufficiently large n.

- ZPP = RP = BPP = P
- MA = AM = NP. In particular Graph Isomorphism and all of statistical zero-knowledge lie in NP∩co-NP.
- S
_{2}P = ZPP^{NP}= BPP^{NP}= P^{NP} - The polynomial-time hierarchy lies in SPP. As a corollary PH
⊆ ⊕P ∩ Mod
_{k}P ∩ C_{=}P ∩ PP ∩ AWPP

_{i}such that

- If φ is not satisfiable then all of the ψ
_{i}are not satisfiable. - If φ is satisfiable then some ψ
_{i}has exactly one satisfying assignment.

This gives a short list containing many Ramsey graphs. We don't
know how to verify a Ramsey graph efficiently so even
though we have the short list we don't know how to create a single
one. Contrast this to the best known deterministic construction that
creates a graph with no clique or independent set of size 2^{(log
n)o(1)}.

We also get essentially optimal extractors. Given an distribution D on
strings of length n where every string has probability at most
2^{-k} and O(log n) additional truly random coins we can
output a distribution on length k strings very close to uniform. The
truly random coins are used both for the seed of the pseudorandom
generator to create the extractor and in applying the extractor
itself.

One also gets polynomial-time computable universal traversal sequences, a path that hits every vertex on any undirected graph on n nodes. The generator will give a polynomial list of sequences but one can just concatenate those sequences. The hardness assumption above won't put the sequence in log space, though we do believe such log-space computable sequences exist. Reingold's proof that we can decide undirected connectivity in logarithm space does not produce a universal traversal sequence though it does give a related exploration sequence.

There are many more implications of full derandomization including other complexity class inclusions, combinatorial constructions and some applications for resource-bounded Kolmogorov complexity.