One-Way Log-Tape Reductions
| dc.contributor.author | Hartmanis, Juris | en_US |
| dc.contributor.author | Immerman, Neil | en_US |
| dc.contributor.author | Mahaney, Stephen R. | en_US |
| dc.date.accessioned | 2007-04-23T18:21:52Z | |
| dc.date.available | 2007-04-23T18:21:52Z | |
| dc.date.issued | 1978-07 | en_US |
| dc.description.abstract | One-way log-tape (1-L) reductions are mappings defined by log-tape Turing machines whose read head on the input can only move to the right. The 1-L reductions provide a more refined tool for studying the feasible complexity classes than the P-time [2,7] or log-tape [4] reductions. Although the 1-L computations are provably weaker than the feasible classes L, NL, P and NP, the known complete sets for those classes are complete under 1-L reductions. However, using known techniques of counting arguments and recursion theory we show that certain log-tape reductions cannot be 1-L and we construct sets that are complete under log-tape reductions but not under 1-L reductions. | en_US |
| dc.format.extent | 786929 bytes | |
| dc.format.extent | 221924 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/TR78-347 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/7465 | |
| 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 | One-Way Log-Tape Reductions | en_US |
| dc.type | technical report | en_US |