|
Abstract : |
This paper investigates the distribution and nonuniform complexity of problems that are complete or weakly complete for ESPACE under nonuniform reductions that are computed by polynomial-size circuits (P/Poly-Turing reductions and P/Poly-many-one reductions). A tight, exponential lower bound on the space-bounded Kolmogorov complexities of weakly P/PolyTuring-complete problems is established. A Small Span Theorem for P/Poly-Turing reductions in ESPACE is proven and used to show that every P/Poly-Turing degree--- including the complete degree--- has measure 0 in ESPACE. (In contrast, it is known that almost every element of ESPACE is weakly P-many-one complete.) Every weakly P/Poly-many-one-complete problem is shown to have a dense, exponential, nonuniform complexity core. More importantly, the P/Poly-many-one-complete problems are shown to be unusually simple elements of ESPACE, in the sense that they obey nontrivial upper bounds on nonuniform complexity (size of nonuniform complexity cores and space-bounded Kolmogorov complexity) that are violated by almost every element of ESPACE. 1, |
