Read on Twitter
I& #39;m going to talk a bit about the P vs NP problem generally, though this thread is a nice introduction to the relevant concepts: https://twitter.com/ApproximateJoe/status/1143679674473734147">https://twitter.com/Approxima...
To get it out of the way: I& #39;m agnostic on whether or not P=NP in actuality. There is a some vague consensus that P is not equal to NP, though the opposing view isn& #39;t entirely heretical (I& #39;ve read that Knuth thinks they might be equal, for instance).
But why should we care? To pitch it in a tweet: there is a class of problems that, if easily solvable, could fundamentally change the world. The solution gives an easy cure for cancer, for instance. It could produce a perfect fusion reactor. Next gen artificial intelligence.
It could take the guesswork out of geoengineering, giving a way to deal with climate change. It& #39;s impossible to understate to massive utility of an algorithm that can solve NP problems.
I chose the quoted tweet because of it& #39;s reference to the million dollar prize associated with the problem. But that money goes to anyone who proves either P=NP or P<>NP.
The possibilities I mention come from the P=NP case, and require a practical algorithm.
The possibilities I mention come from the P=NP case, and require a practical algorithm.
Many people believe such an algorithm cannot exist. Although, many real-world applications *can* be solved by our current algorithms. One of which is illustrated beautifully in the thread I linked to.
I& #39;m talking about all of this now to make three points. First, there are quite a few bored people in lockdown. Second, the world is falling apart at the seams.
And third: new, better algorithms for NP problems could help.
And third: new, better algorithms for NP problems could help.
You don& #39;t even need to prove one of the hardest problems in all of mathematics to produce an improved algorithm. People make their own SAT solvers all the time. And in fact, a SAT solver that is *really good* for real world problems would be worth far more than a million dollars.
If I knew the way to make one, I& #39;d be doing that instead of writing this thread. But I *will* give it some thought from time to time. If you have the mind for it, consider doing the same.
