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