Details

Autor(en) / Beteiligte

• BOOK, R. V
• LUTZ, J. H

Titel

On languages with very high space-bounded Kolmogorov complexity

Ist Teil von

• SIAM journal on computing, 1993-04, Vol.22 (2), p.395-402

Ort / Verlag

Philadelphia, PA: Society for Industrial and Applied Mathematics

Erscheinungsjahr

1993

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• It is shown that if a language recognizable in exponential space is bounded truth-table reducible in polynomial time to a language with very high space-bounded Kolmogorov complexity, then it is bounded truth-table reducible in polynomial time to a sparse language. There are a number of corollaries, including the following: (a) no language with very high space-bounded Kolmogorov complexity is $ \leqslant _{btt}^{\text{P}} $-hard for NP, unless ${\text{P}} = {\text{NP}}$; (b) no language with very high space-bounded Kolmogorov complexity is $ \leqslant _{btt}^{\text{P}} $-hard for the class of languages accepted in exponential time.