One-way functions and the Berman-Hartmanis conjecture

Abstract

The Berman-Hartmanis conjecture states that all NP-complete sets are P-isomorphic each other. On this conjecture, we first improve the previous result of Agrawal and show that all NP-complete sets are les_li,1-1 ^P/poly-reducible to each other based on the assumption that there exist regular one way functions that cannot be inverted by randomized polynomial time algorithms. Secondly, we show that, besides the above assumption, if all one-way functions have some easy part to invert, then all NP-complete sets are P/poly-isomorphic to each other.