On the Isomorphism Conjecture for Weak Reducibilities

作者:

Highlights:

摘要

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 ap-one way functionfand an NP-complete setAsuch thatAandf(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.

论文关键词:

论文评审过程:Received 10 January 1996, Available online 25 May 2002.

论文官网地址:https://doi.org/10.1006/jcss.1996.0068