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.