On the Isomorphism Conjecture for Weak Reducibilities

✍ Scribed by Manindra Agrawal

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 652 KB
• Volume: 53
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0068

✦ Synopsis

According to the isomorphism conjecture all NP-complete sets are polynomial-time isomorphic to each other while according to the encrypted complete set conjecture 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 to each other. In this paper, these two conjectures are translated and investigated for reducibilities weaker than polynomial-time. It is shown 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 one-way, multi-head, oblivious logspace DTMs, the encrypted complete set conjecture is false.

4. Relative to reductions computed by constant-scan logspace DTMs, the encrypted complete set conjecture is true.

It is also shown that the complete degrees of NP under the latter two reducibilities coincide.