Read on Twitter
I'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
To get it out of the way: I'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't entirely heretical (I'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's impossible to understate to massive utility of an algorithm that can solve NP problems.
I chose the quoted tweet because of it'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'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'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'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.
