archives

On Languages with Very High Information Content


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Book, Ronald V. and Lutz, Jack H. (1992) On Languages with Very High Information Content. Technical Report TR92-10, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

On Languages with Very High Information Content
Ronald V. Book and Jack H. Lutz
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.

Subjects:All uncategorized technical reports
ID code:00000016
Deposited by:Staff Account on 01 May 1992



Contact site administrator at: ssg@cs.iastate.edu