Publication Date

5-1992

Technical Report Number

TR92-10

Subjects

Mathematics of Computing

Abstract

The main result of this paper is the following: Any language in ESPACE that is bounded truth-table reducible in polynomial time to a set with very high space-bounded Kolmogorov complexity must be bounded truth-table reducible in polynomial time to a sparse set.

Share

COinS