On Time Versus Space.
Abstract
It is shown that every deterministic multitape Turing machine of time complexity t(n) can be simulated by a deterministic Turing machine of tape complexity t(n)/log t(n). Consequently for tape constructable t(n), the class of languages recognizable by multitape Turing machines of time complexity t(n) is strictly contained in the class of languages recognized by Turing machines of tape complexity t(n). In particular the context sensitive languages cannot be recognized in linear time by deterministic multitape Turing machines.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1975
- Accession Number
- ADA018707
Entities
People
- John Hopcroft
- Leslie Valiant
- Wolfgang Paul
Organizations
- Department of Computer Science, Cornell University