On the isomorphism problem for weak reducibilities

Abstract

The isomorphism conjecture states that all NP-complete sets are polynomial-time isomorphic while the encrypted complete set conjecture states that there is a p-one-way function f and an NP-complete set A such that A and f(A) are not polynomial-time isomorphic. We investigate these two conjectures for reducibilities weaker than polynomial-time. We show that: 1. Relative to reductions computed by one-way logspace DTMs, both the conjectures are false. 2. Relative to reductions computed by one-way logspace NTMs, the isomorphism conjecture is true. 3. Relative to reductions computed by multi-head, oblivious logspace DTMs, crypted complete set conjecture is false. 4. Relative to reductions computed by constant-scan logspace DTMs, the encrypted complete set conjecture is true. We also show that the complete degrees for NP under the latter two reducibilities coincide.