On Log-Tape Isomorphisms of Complete Sets
| dc.contributor.author | Hartmanis, Juris | en_US |
| dc.date.accessioned | 2007-04-23T18:20:06Z | |
| dc.date.available | 2007-04-23T18:20:06Z | |
| dc.date.issued | 1977-07 | en_US |
| dc.description.abstract | In this paper we study $\log n$-tape computable reductions between sets and investigate conditions under which $\log n$-tape reductions between sets can be extended to $\log n$-tape computable isomorphisms of these sets. As an application of these results we obtain easy to check necessary and sufficient conditions that sets complete under $\log n$-tape reductions in NL, CSL, P, NP, PTAPE, etc. are $\log n$-tape isomorphic to the previously known complete sets in the respective classes. As a matter of fact, all the "known" complete sets for NL, CSL, P, NP, PTAPE, etc. are now easily seen to be, respectively, $\log n$-tape isomorphic. These results strengthen and extend substantially the previously known results about polynomial time computable reductions and isomorphisms of NP and PTAPE complete sets. Furthermore, we show that any set complete in CSL, PTAPE, etc. must be dense and therefore, for example, cannot be over a single letter alphabet. | en_US |
| dc.format.extent | 931420 bytes | |
| dc.format.extent | 371661 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR77-318 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/7439 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | On Log-Tape Isomorphisms of Complete Sets | en_US |
| dc.type | technical report | en_US |