One-Way Functions and the Berman-Hartmanis Conjecture
Manindra Agrawal, Osamu Watanabe · 2009
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 lesli,1-1P/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.