# Is the Berman-Hartmanis Conjecture Solved?

The Berman-Hartmanis conjecture more or less states that if one-way functions exist, there are some problems in $NP$ which cannot be polynomially reduced to $NP$-complete (cf. Ker-I Ko, A Note on One-Way Functions and Polynomial-Time Isomorphism).

Since the Cook-Levin theorem states that $NP$ is polynomial-time reducible to $NP$-complete.

Does the Berman-Hartmanis conjecture state anything about the converse statement? I.e. if $NP$ is polynomial-time isomorphic to $NP$, then one-way functions do not exist?

It seems to me that proving the converse and proving the non-existence of one-way functions proves the $P=NP$ problem.

Furthemore, is the Berman-Hartmanis conjecture solved?

• Reading here I get a very different view of what the Berman-Hartmanis conjecture is. I think you might be confusing polynomial reduction and polynomial isomorphism. – jmite Jun 11 '14 at 17:38
• I got my information mostly from: cse.iitk.ac.in/users/manindra/isomorphism/… and a paper by Ker-I-Ko... I may have overstated some things. – user13675 Jun 12 '14 at 18:02

• Do you have the link or a reference to the article that shows that if BH holds $P\neq NP$? thx. – user13675 Jun 12 '14 at 17:19