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.
- Title
- Isomorphisms and 1-L reductions
- Creators
- Eric W Allender - Department of Computer Science, Rutgers University, New Brunswick, New Jersey 08903, USA
- Publication Details
- Journal of computer and system sciences, Vol.36(3), pp.336-350
- Date published
- 1988
- Publisher
- Elsevier Inc
- Academic Unit
- Computer Science (SAS)
- Language
- English
- Resource Type
- Journal article
- Identifiers
- 991031654765104646