0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 2014 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, 2014 at 18:02

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2014 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, 2014 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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