Publication Date

4-1990

Technical Report Number

TR90-04

Subjects

Theory of Computation, Mathematics of Computing

Abstract

Every language that is polynomial time many-one hard for ESPACE is shown to have unusually small complexity cores and unusually low space-bounded Kolmogorov complexity. It follows that the polynomial time many-one complete languages form a measure 0 subset of ESPACE.

Share

COinS