5 ms·
In my mind I always regard P/NP in the same category as the Riemann Hypothesis^. That has been open since 1859 (160 years) and shows no signs of cracking. So in
by jacobkg 7y ago
In my mind I always regard P/NP in the same category as the Riemann Hypothesis^. That has been open since 1859 (160 years) and shows no signs of cracking. So in other words we may be in for a long wait.
^Perhaps because one of the hypothesized examples of a hard problem is the factoring of multiples of large primes (though not proved NP Complete). Or perhaps because they are both extremely famous open problems.
- hinkley 7y agoOne of the things that slows scientific progress is the lack of cross-discipline learning. Every so often you hear about someone taking an old concept from another field and applying it. Quite a few breakout companies have combined interdisciplinary knowledge into one product and made a mint. So many people are affected by NP complete problems that you'd think that someone would have a problem that appeared simpler on the surface and gave insights into a P solution, but either nobody has, or the right phrasing about it has caught nobody's attention. There's an XKCD lamenting something pretty similar. You solved some unsolved problem but nobody will ever know because it's buried in a bug fix for your obscure little product.
- empath75 7y agoIt’d be amazing if we found some polynomial solution to an np complete problem buried in some kids Minecraft mod 10 years from now.
- fovc 7y agohttps://m.xkcd.com/664/ https://m.xkcd.com/664/
- raverbashing 7y agoI think Academia is more likely to criticize your technique because it doesn't generalize to any ring or you didn't prove a certain assumption you had. Of course the real bug is in some IEEE 754 quirk you forgot to consider.
- hinkley 7y agoThat’s the one. The alt text: > Some engineer out there has solved P=NP and it's locked up in an electric eggbeater calibration routine. For every 0x5f375a86 we learn about, there are thousands we never see.
- intuitionist 7y agoWe know much less about P vs NP than we do about RH; we can prove weaker versions of RH (e.g. the prime number theorem) and analogues for other number systems (the Weil conjectures). This is unsurprising, since it hasn’t influenced math research for 160 years. Maybe someone will separate P and PSPACE before P and NP, or maybe they’ll fall at once to some brilliant new technique.