On the Isomorphism Problem for Weak Reducibilities (Extended Abstract)
Manindra Agrawal · 1994
The isomorphism conjecture states that all NPcomplete 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.