@inproceedings{669dbfef7d644bc689ed8be9c00e3bd0,
title = "Isomorphisms and 1-L reductions",
abstract = "All sets complete for NP under 1-L reductions are complete under length-increasing, invertible, and “almost one-one” ≤m p reductions. All sets complete for PSPACE under 1-L reductions are p-isomorphic.",
author = "Allender, {Eric W.}",
note = "Funding Information: ?Portions of this research were c~rried out while the author was supported by NSF grant MCS 81-03608. Publisher Copyright: {\textcopyright} 1986, Springer-Verlag.; Structure in Complexity Theory Conference, 1986 ; Conference date: 02-06-1986 Through 05-06-1986",
year = "1986",
doi = "10.1007/3-540-16486-3_86",
language = "English (US)",
isbn = "9783540164869",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "12--22",
editor = "Selman, {Alan L.}",
booktitle = "Structure in Complexity Theory - Proceedings of the Conference held at the University of California",
address = "Germany",
}