Isomorphisms and 1-L reductions

Eric W Allender

doi:10.1007/3-540-16486-3_86

Back

Book chapter

Peer reviewed

Isomorphisms and 1-L reductions

Eric W Allender

Structure in Complexity Theory, pp.12-22

Lecture Notes in Computer Science, Springer Berlin Heidelberg

06/02/2005

DOI: https://doi.org/10.1007/3-540-16486-3_86

Abstract

Complexity Class

Marked Vertex

Input Symbol

Invertible Function

Turing Machine

All sets complete for NP under 1-L reductions are complete under length-increasing, invertible, and “almost one-one” ≤mp reductions. All sets complete for PSPACE under 1-L reductions are p-isomorphic.

Metrics

6 Record Views

Details

Title: Isomorphisms and 1-L reductions
Creators: Eric W Allender
Publication Details: Structure in Complexity Theory, pp.12-22
Date published: 06/02/2005
Series: Lecture Notes in Computer Science
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Book chapter
Identifiers: 991031654490904646