P Vs NP Problem In A Nutshell.
One of the unanswered questions in computer science is a problem called P vs. NP. In 2000 the Clay Institute offered 1 Million dollars each for the solutions to seven key problems, called the Millennium Prize problems. Of the seven problems, P vs. NP is both the most recently conceived -- in 1971, and by far the easiest one to understand and explain.
Background:
Computer scientists figure out how to program their computers to solve all the world's problems. At first, these programs are usually too complex for the computers to optimally execute.
The complexity of these programs revolves around two aspects, either increasing the processing power or figuring out a smarter way to solve the given problem. A rule of thumb is that the time complexity of a computer program is inversely proportional to its space complexity.
Hence, sometimes the first program anyone could think of for a particular problem would be very slow, but then over time people would come up with cleverer ways to make it faster, or at least that happened for some problems.
For instance, if you want to sort an array of numbers using bubble sort it would have an upper bound of O(n^2) while merge sorts algorithm has an upper bound of O(n log(n))
However, for other problems, nobody was coming up with faster programs. Computer scientists figured out that some programs like multiplication had really fast programs, and for others, like playing absolutely perfect chess there were no faster programs. Therefore understand the situation better they started sorting the problems into classes based on how fast the program can solve them. Hence, P and NP are two computational classes in the computational complexity zoo.
What is P VS Np?
P is a class that includes all the problems that can be solved by a reasonably fast program, like multiplication or addition.
A superset of P is a class called NP. These are all the problems where if you're given a correct solution you can at least check it in a reasonable amount of time but computing the correct solution itself is not possible in polynomial time. Like Factorization can take a long time to solve but if you already know the factors then, checking it for mistakes is pretty quick.
NP contains lots of important problems like vehicle routing, scheduling, circuit design, and databases.
Interestingly, sometimes we get lucky and find that an NP problem is actually a part of P and we'd have our fast program. But, for a lot of them that didn't seem to be happening.
So people started to wonder whether everything in NP would turn out to be in P or if there were some NP problems that were truly harder than the ones in P.
Therefore, a subset of NP problems is P problems, where a way to check an answer is to go through the process of finding it yourself. Like, if I were to tell you that the answer to 71 x 3 is 213,
how would you check whether I'm right? You'd probably just multiply 71 by 3 yourself because it's fast to do it. Hence, NP contains some problems which can be solved in polynomial time (P problems) and other problems are the ones which can or can not be solved in polynomial time. As far as we know, there could be a clever way of solving such problems, much faster but right now we don’t know that.
So, in a nutshell, the question is:
Does being able to quickly recognize correct answers mean there's also a quick way to find them?
If the answer is yes than, a lot of important puzzles we've been struggling with are gonna turn out to be easy for computers to solve and we'd have a lot of miracle answers almost overnight and also the encryption we use for things like online banking would be easy to crack, because it's based on NP problems.
Computational Complexity Vs Problem Size:
Well, we're really talking about how the difficulty scales up as you make the problem bigger and bigger. For example, finding prime factors gets harder as the problem size increases.
We've been making computers exponentially faster as time goes on, 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.
Like, multiplication problems are pretty easy for computers, even with enormous numbers. As the numbers get bigger, multiplying them just doesn't get harder very fast.
The Computational Complexity Zoo:
In the early 1970s, complexity researches realized that dozens of those NP problems they were struggling with were essential all the same problem!
These are called "NP-complete" problems. NP-complete means that these problems include all the really hard parts of every NP problem.
Theoretically, a fast program for solving any NP-complete problem could be used to solve every problem in NP. The whole class would instantly collapse. So, amazingly, Sudoku is hard because it involves, literally, the same NP-complete task that makes protein folding hard.
Therefore, solving the NP-complete task of Sudoku in polynomial time would solve the fast protein folding which in turn would help us cure cancer.
As the field of computational complexity has developed, we've discovered a lot of complexity and it includes a complicated "zoo" 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.
This whole upper area 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 right answers, it's easy to exclude wrong answers, which may or may not be the same of NP
And then there's "P-SPACE", the class of problems that can be solved given unlimited time, 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 actually be the same as P.
And then there's a quantum computing analog of BPP called BQP.
The amazing thing about this whole complexity zoo is that we're talking literally about what can be computed in a given amount of space, and time.
We're not just looking at the nature of computation here, we're looking at the nature of space and time themselves.
Conclusion:
So why has it been so hard to prove P vs. NP one way or the other? Well, fun fact, proving things is an NP problem.
The P vs. NP question itself is one of these problems. So yeah, this might be difficult, or not? we don't know.
Scott Aaronson, a complexity researcher 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 the solution once it's found. Everyone who could appreciate a symphony would be Mozart; Everyone who could follow a set-by-step argument would be Gauss."
References:
http://www.scottaaronson.com/papers/pnp.pdfhttps://www.win.tue.nl/~gwoegi/P-versus-NP/sipser.pdf http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdfhttp://www.claymath.org/sites/default/files/pvsnp.pdfhttps://www.youtube.com/watch?v=YX40hbAHx3s
This article has been inspired by the material in the following videos. These videos are the best content available on P vs NP and this article aims to elaborate and explain the details which might have been overlooked in the following videos:
https://www.youtube.com/watch?v=9MvbNPQiEE8
https://www.youtube.com/watch?v=YX40hbAHx3ss
https://www.youtube.com/watch?v=eHZifpgyH_4