TR09-019 Authors: Agrawal Manindra, Osamu Watanabe

Publication: 16th March 2009 07:53

Downloads: 761

Keywords:

We study the Isomorphism Conjecture proposed by Berman and Hartmanis.

It states that all sets complete for NP under polynomial-time many-one

reductions are P-isomorphic to each other. From previous research

it has been widely believed that all NP-complete sets are reducible

each other by one-to-one and length-increasing polynomial-time

reductions, but we may not hope for the full p-isomorphism due to the

existence of one-way functions. Here we showed two results on the

relation between one-way functions and the Isomorphism Conjecture.

Firstly, we imporve the result of Agrawal [Agrawal, CCC'02] to show

that if regular one-way functions exist, then all NP-complete sets are

indeed reducible each other by one-to-one, length-increasing and

P/poly-reductions. A consequence of this result is the complete

description of the structure of many-one complete sets of NP relative

to a random oracle: all NP-complete sets are reducible each other

by one-one and length-increasing polynomial-time reductions but

(as already shown by [Kurtz etal, JACM 95]) they are not P-isomorphic.

Neverthless, we also conjecture that (different from the random oracle

world) all one-way functions should have some dense easy parts, which

we call P/poly-easy cylinders, where they are P/poly-invertible.

Then as our second result we show that if regular one-way functions

exist and furthermore all one-one, length-increasing and

P/poly-computable functions have P/poly-easy cylinders, then all

many-one complete sets for NP are P/poly-isomorphic.