Completeness and Weak Completeness under Polynomial-Size Circuits

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/Poly-Turing-complete problems is established. A Small Span Theorem for P/Poly-Turing reductions in ESPACE is proven and used to show thateveryP/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 beunusually simpleelements of ESPACE, in the sense that they obey nontrivialupperbounds on nonuniform complexity (size of nonuniform complexity cores and space-bounded Kolmogorov complexity) that are violated by almost every element of ESPACE.

Authors

• David W. Juedes
• Jack H. Lutz

Keywords

No keywords are indexed for this paper.