Agrawal, M.
(1994)
*On the isomorphism problem for weak reducibilities*
Proceedings of IEEE the Ninth Annual Structure in Complexity Theory Conference, 1994
.
pp. 338-355.

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?...

Related URL: http://dx.doi.org/10.1109/SCT.1994.315790

## 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.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to IEEE. |

ID Code: | 95353 |

Deposited On: | 07 Nov 2012 04:46 |

Last Modified: | 07 Nov 2012 04:46 |

Repository Staff Only: item control page