Solving problems is the bread and butter of computing and mathematics in general. Without that urge of solving problems our world will not exist in our present form. Going to work and/or school, cooking some food, going on vacations, etc. are still forms of problems even if you don't take notice of that 🙂.
In this article I try to talk in a way such that even a non-computer science inclined person can understand.
I talk about the deepest unanswered question in computer science and maybe in all of mathematics; A problem called P vs NP and I want to talk about how ideas from computing show up in the everyday world around us and how very difficult problems like protein folding(process/method used for curing cancer) that seem so different from cross-word puzzles share a common core difficulty that turns out to be a lot like Sudoku.
Basically all of them are one and the same problem.
In 2000 the Clay institute offered $1 million each for the solutions to 7 key problems in math; The Millennium Prize Problems.
These are profound and difficult problems and for most of them it takes a lot of specialized knowledge to even understand the question. Of the 7 problems P vs NP was both the most recently conceived in 1971 and by far the easiest one to understand and explain(kind of why I maybe decided to write for this particular problem 🙂)
In March 2010 the Clay institute awarded the first of its 7 prizes to Grigori Perelman for the solution to the Poincare Conjecture.
So what is the P vs NP question actually?
Some history…
Back in the 70s computer scientists were busily figuring out how to program their retro cabinet-sized computers to solve all the world’s problems. Sometimes the first program that anyone could think of for a particular problem will be unworkably slow but then overtime we("we" here as in the computer science community as a whole) will come up with clever ways to make it faster. That happened for some problems, for others nobody was able to come up with faster programs.
To get a handle on the situation we started sorting the problems into classes; based on how fast a program could solve them. For problems like multiplication they had really fast programs and for others like playing absolutely perfect chess they figured out that there was just no fast program but for some in between they weren’t sure whether there was a fast way to do it so they kept trying…
This is where P vs NP come in. Skipping a ton of details P is a class that basically include all the problems that can be solved by a reasonably fast program like multiplication or putting names in alphabetical order and then around and including P we sort of discovered a class called NP; that’s all the problems where if you are given a correct solution you can at least check it in a reasonable amount of time.
NP was a new and total maddening class as it contained a lot of important problems like vehicle routing, scheduling timetables, problems in circuit design and databases. Often we might find out that an NP problem was actually part of P and we will have our fast program but for a lot of them that didn't seem to be happening. So we started to wonder whether everything in NP will turn out to be in P(P = NP) or if there were some problems that were truly harder than the ones in P(P != NP); That's the P vs NP question.
If all the NP problems are really in P then a lot of important problems we've been struggling with are going to turn out to be easy for computers to solve; problems connected to biology and curing cancer, problems in business and economics, we'll have a lot of miracle answers almost overnight but sadly the security used for our online banking and other financial transactions will be easy to crack as it's based on NP problems.
Let's think about these problems as puzzles. I like puzzles as what makes a puzzle a puzzle is that it's a problem where you can give away the answer, and that's what NP means.
For example with Sudoku; Sudoku puzzles can take a long time to solve but if I give you a solved grid, checking it for mistakes is pretty quick .
Outside of NP are problems where it's hard to even check whether the answer is wrong or right.
For example what's the best move to make in this chess game?
I could tell you the answer but how would you know whether I am right? You wouldn't because finding out requires a calculation so enormous that there's a pretty good argument we'll never be able to build a computer that could do it. To me that's not a good puzzle because it's practically impossible to know whether you've solved it.
On the other side are all the reasonable and solvable problems in P. These are clearly also in NP because one way to check an answer is to go through the process of solving it yourself. Like if for example I tell you that the answer to 72x4 is 288, how would you know whether I am right? You would probably multiply those numbers yourself to check because it's fast to do it.
But Sudoku is "different", or at least, we think it is. It seems like solving a Sudoku grid is a lot harder than checking a solution, but in fact nobody has been able to prove it yet. As far as we know, there could be a clever way of playing Sudoku, much much faster.
So that's the question; Does being able to quickly recognize correct answers means there's also a quick way to find them? Another way of putting is asking Is P = NP or P != NP(Is P equal to NP or not equal NP)?
Nobody knows for sure, but either way, figuring out exactly how this works would teach us something important about the nature of computation.
It gets weirder from here but first: three important details.
1. Levels of growing difficulty
You might be thinking: hey, Sudoku is tough and all but it's not that hard. What's the big deal about it? Well we're really talking about how the difficulty scales up as you make the problem bigger and bigger.
Like how much harder is a 100x100 Sudoku grid than a standard 9x9 grid?
We've been making computers exponentially faster as time went by, so, for problems that don't get exponentially harder as they get bigger, all we have to do is wait for computers to get more powerful and then, even huge versions of those problems will be easy to solve by a computer.
Multiplication for example; even with huge or enormous numbers multiplication problems are pretty easy for computers. As the number gets bigger, multiplying them doesn't just get any harder very fast.
These days, the phone in your pocket is what would have been referred to in the 1970's as a "supercomputer".(On a tangent here; remember they used those computers in the 1970's to send a man to the moon but now the "supercomputer" in your pocket just sits there and/or helps you to like funny pictures or get laid, but that's a story for another time 😬)
You'd have to make up truly huge multiplication problems to stand up to all the computational power we've got now.
Lots of familiar puzzles like Rubik's cube and mazes are in the same camp; hard for humans, but easy work for computers.
And then there's Sudoku. Computers can usually solve a 9x9 grid in a few milliseconds even though humans find them challenging but as you make the grid bigger and bigger the problem just gets really hard, rapidly getting out of reach for even the most powerful computers.
2. Meaning of P
P stands for "Polynomial time". In P the number of steps required to solve a problem which is also the amount of time it takes to solve that problem is a polynomial function of its size. So if you have a program to solve a particular problem and increase the size of the input of that program a little, the time it takes to run the program to solve that problem increases... but in a reasonable way(i.e it does not double).
"Polynomial" is a mishmash of Greek and Latin meaning "many names", which is, regrettably a pretty typical example of Maths flair for unhelpful terminology 😅.
Anyway, polynomials are functions involving n or n2(n-square) or n to other powers like these; 7n5-6n3+5n2
But importantly they're not exponential functions like 2n, which gets to be a ton of steps really fast as n goes up, a lot quicker than n2.
So that's P, it's problems like mazes and multiplication where the number of steps required isn't that bad compared to the size of the problem.
2.5. NP
NP is all about polynomial time "checking". NP stands for "Non deterministic Polynomial time", which being math terminology is almost a mean spirited way of saying that if you had a wizard or witch inside of the computer such that it could check all possible solutions at the same time to give you an answer, then you could find a correct solution in polynomial time.
3. Current state of the art
Pretty much everybody think it's obvious that NP is harder than P and that it contains more problems than P, it's just that we haven't been able to prove it.
The bad news for fast solutions came in the early 1970's when complexity researchers realized that dozens of NP problems they were struggling with were essentially all one and the same problem(with some easy polynomial time complications thrown in here and there).
These are called NP-complete problems, and since the first batch in the 70's we've added Sudoku and protein folding, and problems underlying puzzles and games like Battleship, FreeCell, MasterMind, Tetris, Minesweeper, and making up crossword puzzles. Even classic video games like SuperMario Bros and Metroid turn out to be connected to NP-complete level traversal problems.
NP-complete is yet another maths term meaning that these problems include all the really hard parts of every NP problem. Id a fast program for solving any NP-complete comes to existence then it can be used to solve every problem in NP. The whole class would instantly collapse.
So amazingly as you can see, Sudoku is hard because it involves, literally, the same NP-complete task that makes protein folding hard.
If you come up with a profoundly faster way to play Sudoku let me know, okay? because fast protein folding would help scientists cure cancer(And we'll have our million dollars 😉).
Unfortunately the fact that a bunch of smart people have all been unsuccessful coming up with fast programs to solve what turned out to be, essentially, one and the same problem, looks like a pretty good clue that either it's impossible or the fast programs just aren't out there.
So why has it been so hard to prove P vs NP one way or the other? Well, fun fact, the exercise of proving things is an NP problem. So the P vs NP question itself is one of these problems(Do you see the paradox?). So as you can see this might be difficult... or not? We don't know.
As the field of computational complexity has developed, we've discovered a lot of complexity. The P vs NP question turns out to be the main attraction in a huge and complicated universe of complexity classes.
Beyond NP there are even harder classes of problems like EXP--the class of problems including figuring out the best move in chess that takes exponential time to even check. That whole side of problems that are at least as hard as NP-complete is called "NP-hard".
There's also Co-NP-- the class of problems where instead of being easy to check for correct answers, it's easy to instead exclude wrong answers, which may or may not be the same as NP(remember... we don't know if they're equal or not equal to each other).
There's also P-SPACE-- the class of problems that can actually be solved given unlimited time(which we don't have), but using only a polynomial amount of space for memory.
There are also problems that can be solved probabilistically in polynomial time. That class is called BPP, and it may or may not be the same as P. There's also a quantum computing analog of BPP called BQP.
All over the spectrum there are complicated little classes that would take a lot of explaining. We know there's an exponential hierarchy and there's also a polynomial hierarchy and beyond all that there are problems that are just not solvable by any computer in any amount of time or space(Example is the Halting Problem).
Conclusion
The amazing thing about this whole mess of complexity is that we're literally talking about what can be computed in a given amount of space and time. We're not just talking about the nature of computation here, we're looking at the nature of space and time themselves.
This mess of computational complexity classes, I think, ultimately has implications for physics and biology, and for our basic understanding of everything.
As an example of those implications, here's how Scott Aaronson a complexity researcher who was at MIT, explains his intuition about P vs NP:
"If P were equal to NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps", no fundamental gap between solving a problem and recognizing a solution once it's found. Everyone who could appreciate a symphony would be Mozart or Beethoven; everyone who could follow a step-by-step argument would be Gauss or Newton."
The world around us, the nature of living things and ideas, of art and genius is moulded around the deep structure of computation.
In a very real way, something connected to P vs NP shows up in the struggles of scientists and artists.
Chopin once said: "Simplicity is the final achievement. After one has played a vast quantity of notes and more notes, It is simplicity that emerges as the crowning reward of art". Computer scientists and to an extent mathematicians have been figuring out to solve all the world's problems with the help of computation but even Einstein, in his personal research for the Theory of Everything said this; "Everything should be made as simple as possible but not simpler."
Adapted from The Computational Complexity Zoo.
Top comments (0)