Hacker News Reader

Comment by fiddlerwoaroof | Hacker News Reader

Wouldn’t it prove the opposite namely that P equals NP?

No, if you can prove that a secure hash function exists, then you have proved that P != NP. (This is what alexbecker said.)

If you can prove P = NP, then you have proved that no secure hash functions exist. (This is the contrapositive.)

For convenient definitions of "secure" :-). "Unscrambling" a particular function could be in P but still effectively intractable.

(For a fun angle not related to complexity, the algorithm itself could be so large that it wouldn't fit in the observable universe without breaking the Bekenstein bound.)

And it has been a long time since I did proof theory, but is there the possibility of a non-constructive proof but no actual examples no matter how long you keep enumerating algorithms? Or a non-constructive proof, but no constructive proof? In that case there could be a "perfect heuristic"...

Oops, this is what I get for not reading carefully :) But this is interesting: it implies, if I'm not mistaken, it implies that we haven't ever proven that a function takes exponential time, just that we haven't found any algorithms for certain problems faster than exponential time. I hadn't considered P != NP this way before...

No, we know that P != EXP_TIME, by the time hierarchy theorem - i.e. we know some problems (and we do have concrete examples) take exponential time. What we don't know is that there exists a problem that requires exponential time (or otherwise greater than polynomial) where we can create a proof that a answer is correct which is checkable in polynomial time.

https://en.wikipedia.org/wiki/Time_hierarchy_theorem

I think you mean... P = NP. Which is very unlikely as we could do away with mathematicians if that were true.

Seems unlikely, but not proven. That's the point. I dunno about 'do away with mathematicians'.

Yeah, I just thought that showing how to solve a best-case exponential function in polynomial kind was the sort of thing that would prove P = NP (I dictated this before, so NP came out as MP)

Reply on news.ycombinator.com