3 ms·

Chris, I am a bit over my head usually with P=NP, since it's not my area and I have to warp it before it is. One question I would have on your comment is: What

Chris, I am a bit over my head usually with P=NP, since it's not my area and I have to warp it before it is. One question I would have on your comment is: What kind of proof or counterexample for P ?= NP would in fact influence our study of hash functions? This is a subjective question of course, but essentially I am wondering what approach to P ?= NP might introduce new mathematics that indeed would have something to say about hash functions.

ChrisLomont 6y ago
>What kind of proof or counterexample for P ?= NP would in fact influence our study of hash functions? None. Hash functions are almost all O(1) to invert, that is, constant time. It's just we designed that constant to be prohibitively large. And hash functions are not generally based on NP hard problems - they're based on bit mixing, which for all common hash functions are completely orthogonal to the question of P and NP. Quantum computing, via Grover's algorithm, did impact hash functions one and all, since it allows searching N unstructured items in O(sqrt(N)) time, while classical computers require O(N) time. But this simply turns a 512 bit hash into a 256 bit hash, still intractable. Again, however, this has nothing to do with P?=NP. For a problem to be changed by P?=NP, since most think P != NP, that problem must be in NP/P, and hash functions are not (almost ever, and no common ones) from that class of problems. Also the problem has to part of an infinite family of such problems with unbounded sizes. Hash functions again are not in this class. Of course, it may be that we can build computers in the future with closed timelike loops (CTL), in which case all problems are constant time, and that may prove for that class of machines that the complexity hierarchy collapses, but that is a long time off, if ever. We may be able to build machines that exploit topological quantum field theories (TQFTs) some day, like in Friedman's work, and again, that may break things, but again that is a long time off, if ever. I'd personally bet on P!=NP being a fundamental law of physics, built into the fabric of the universe, in the It from Bit idea from Wheeler and others. I think this is becoming more and more the mainstream science belief, as the universe is looking more and more like computation.

ChrisLomont 6y ago

>What kind of proof or counterexample for P ?= NP would in fact influence our study of hash functions? None. Hash functions are almost all O(1) to invert, that is, constant time. It's just we designed that constant to be prohibitively large. And hash functions are not generally based on NP hard problems - they're based on bit mixing, which for all common hash functions are completely orthogonal to the question of P and NP. Quantum computing, via Grover's algorithm, did impact hash functions one and all, since it allows searching N unstructured items in O(sqrt(N)) time, while classical computers require O(N) time. But this simply turns a 512 bit hash into a 256 bit hash, still intractable. Again, however, this has nothing to do with P?=NP. For a problem to be changed by P?=NP, since most think P != NP, that problem must be in NP/P, and hash functions are not (almost ever, and no common ones) from that class of problems. Also the problem has to part of an infinite family of such problems with unbounded sizes. Hash functions again are not in this class. Of course, it may be that we can build computers in the future with closed timelike loops (CTL), in which case all problems are constant time, and that may prove for that class of machines that the complexity hierarchy collapses, but that is a long time off, if ever. We may be able to build machines that exploit topological quantum field theories (TQFTs) some day, like in Friedman's work, and again, that may break things, but again that is a long time off, if ever. I'd personally bet on P!=NP being a fundamental law of physics, built into the fabric of the universe, in the It from Bit idea from Wheeler and others. I think this is becoming more and more the mainstream science belief, as the universe is looking more and more like computation.