I thought perhaps three of the Millennium problems had been solved, and the apocalypse were here.
BTW, for those interested in P=NP and not so much in the direct mathematical research, one interesting way to approach is via hash functions. If we had P=NP, then hash functions would be more easily invertible (eh, left or right invertible). I think in polynomial time. Sorry for the "I think", this isn't my field and I try to find ways to reinterpret it.
P,NP, and the invertability of most hash functions are not related, as far as is known. Most one-way functions of use are not known to be NP hard or NP complete, so having P=NP or P != NP would not affect currently widely used hash functions.
While not NP complete, reverting a hash function is in NP(), so it is very much affected if P=NP.
() Ok obviously it can't be in NP as it's not a decision problem, but asking "is there a preimage starting with 1, with 1A, etc." _is_ in NP. From the it's trivial to generate a preimage in P.
Inverting hash functions isn’t in NP, except that it’s constant time, so it’s also trivially in P. Thus P=NP is irrelevant. It’s just the constant is large. Since each common hash function is fixed size, inverting them is fixed size.
For a problem to be of interest regarding the P=NP question, the problem needs to have arbitrarily large size. 3-SAT can be arbitrary sized, thus is a candidate to ask if it’s NP hard, complete, etc. If we consider 3-SAT with fixed, bounded size, then 3-SAT is constant time.
For example, inverting SHA-512 requires at most on order of 2^512 ops to invert. This is constant time, not even polynomial time.
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.
>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.
I thought perhaps three of the Millennium problems had been solved, and the apocalypse were here.
BTW, for those interested in P=NP and not so much in the direct mathematical research, one interesting way to approach is via hash functions. If we had P=NP, then hash functions would be more easily invertible (eh, left or right invertible). I think in polynomial time. Sorry for the "I think", this isn't my field and I try to find ways to reinterpret it.