Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
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.