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?

  • 1
    $\begingroup$ 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. $\endgroup$ – jmite Jun 11 '14 at 17:38
  • $\begingroup$ 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. $\endgroup$ – user13675 Jun 12 '14 at 18:02

The conjecture remains open. Also there is a proof that shows that if the conjecture is true, then P=/=NP. To my knowledge no one has proven the opposite, that if the converse is true then P=NP, to be true.

  • $\begingroup$ Do you have the link or a reference to the article that shows that if BH holds $P\neq NP$? thx. $\endgroup$ – user13675 Jun 12 '14 at 17:19
  • 1
    $\begingroup$ Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis (sciencedirect.com/science/article/pii/0022000082900022 ) , basically it shows that if the conjecture is false, not the converse though, then P=NP, and the existence of the thing that proves the conjecture false is required for P=NP to be true. $\endgroup$ – lPlant Jun 12 '14 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.