P vs NP Problem
If it's easy to check if the solution to a problem is correct, is it also easy to solve the problem?
Friday 18th August 2023, 23:47 BST
Does P = NP?
This seemingly simple enough problem on the outside has been labelled by writer Larry Hardesty at MIT as, “the most important outstanding question in theoretical computer science”.
Being one of the seven-millennium prizes, its proof (or disproof) holds $1,000,000 in its clutches. In fact, of these seven problems, the P=NP problem deserves special attention as its proof would in turn prove or disprove all 7 problems. ($7million, nice! - actually, $6milllion, since one of the seven has already been solved)
A survey executed in 2002 showed 61 out of 70 leading mathematicians and computer scientists believed that P ≠ NP. Many of the remaining nine further disclosed they only chose otherwise to be on the contrary.
So why does the question continue to hold such significance?
To understand this we first need to confront what the question means. Taken at face value the question seems deceptively simple.
“Well, if n = 1, then yes P = NP”.
While you’re not factually incorrect, this problem happens to be slightly more complex.
Put simply the question is:
If it is easy to check if the solution to a problem is correct, is it also easy to solve the problem?
So what do P and NP really mean?
P and NP refer to ‘complexity classes’ of problems. In simpler terms, how difficult a problem is for a computer to solve a problem based on the amount of time and memory it would need to do this.
P problems are a subset of relatively easy problems, while NP problems are a set of problems that seem to be very, very hard problems. The question here is are these very, very hard problems in fact just relatively easy problems in disguise?
P problems are formally defined as, “problems that have algorithms that can be computed in polynomial time”.
polynomial time - Polynomial time simply means, If N is defined as the number of inputs to an algorithm, then a polynomial function of N (e.g N^3 or N^4 + 2N^6 ect.) is the amount of time taken for the computer to return an answer.
Examples of P problems include linear searching, matrix multiplication, merge sort, and other relatively simple algorithms.
However, NP (Non-deterministic Polynomial) problems are formally defined as “problems that can be verified in polynomial time but may take an exponential number of steps to solve”. While solving the problem could take an exponential number of steps, if given the solution it can be easily verified.
exponential - This means that as the input value x increases, y increases at a much faster rate shooting off to infinity.
A common example of this would be a game of sudoku. Completing a grid of Sudoku often takes a considerable amount of time, however checking your correct answer at the end would take no more than a few minutes.
Why is this a problem?
Computers may be almost 10 million times faster than the human brain but at an exponential scale, problems become too large to even compute within a reasonable amount of time.
If a P problem were to have 100 inputs (N=100), and the algorithm was proportional to n^3, It would take around 3 hours for the computer to solve.
However if an NP problem, with algorithm completion time proportional to 2^n, were to have 100 inputs, It would take the computer 300 quintillion years to solve. Considering the universe is approximately 13.77 billion years old, it would take the computer around 2.2*10^10 lifetimes of the universe to solve. I don’t think I can schedule that in for next week.
But the question remains, why would its’ proof be significant? Sure, proving it would be cool and would make you a few million dollars richer, but why else? (as if that wasn’t enough)
Well, proving P to be equal to NP would hold more wonders than just the joy of a mathematician and computer scientist. MIT complexity researcher, Scott Aaronson made the remark:
"If P were equal to NP then the world would be a profoundly different place than we assume it to be. There would be no special value in creative leaps. no fundamental gap between solving a problem and recognising the solution once it is found"
‘NP Complete’
One key thing to note here is when NP is referred to in the question ‘Does P = NP?’, the NP problems that are actually being highlighted are NP-complete problems. These make up another subset consisting of the most difficult NP problems out there; None of which have ever been proven to be P problems. There have been NP problems that were proven to be P problems, one of them being ‘finding primes’.
If it were to be proven that even 1 NP-complete problem was, in fact, a P problem, it would mean they all were and would revolutionise the way we approach seemingly impossibly difficult problems.
NP complete problems include the infamous ‘Travelling Salesman Problem’, ‘nxn sudoku’, and even ‘Candy Crush’!
Optimisation
Optimisation is also an NP problem. Travel routing, good production, job scheduling, etc. would be easily optimised creating an ‘optimal’ industry. No waiting in traffic, or waiting days for a package.
In turn, there would be massive advancement in machine learning as problems that are easy to check would become just as easy to solve.
Sudoku’s efforts towards curing cancer
Although the correlation seems non-existent, the protein folding problem proves to be NP-complete just as general sudoku is. So if you could solve general sudoku in polynomial time, protein folding can also be solved much more efficiently. This would massively contribute to the efforts in curing cancer. So if you happen to find a super efficient way to solve sudoku, let someone know, you may be more than a sudoku master!
A 9x9 sudoku grid is not NP-complete, however, the general concept of an nxn sudoku grid is. Above are two puzzles, one possibly slightly more difficult than the other. However, checking the answer to either would undoubtedly be easier than solving the problems themselves. But what if it were as easy to solve as it is to check? - in other words, does P = NP?
of course. you can still have a go.
Public Key Cryptography
“All of the assumptions as to public key systems' security are based both upon the idea that P does not equal NP and thus that there is no polynomial solution to the algorithms, and the hope that there is not some way to solve the problem”
problems with public key - Stanford Computer Science
In most cryptography the problem of finding the decryption key is an NP search problem.
Essentially all the cryptography currently in use on the internet which ensures safe transaction of money online and online shopping would be broken if P were to = NP. In this light, it’s safe to say the grass isn’t always greener on the other side.
The P vs NP problem remains unsolved today and is still frequently referred to as one of computer science’s ‘deepest unanswered questions’.
So why is it so hard to prove?
Well, the fact is, proving things itself turns out to be an NP problem. This makes the question ‘Does P = NP?’ an NP problem too! This means it’s either undeniably very difficult to prove or actually very simple. We just don’t know.
I believe ruling out the possibility that P could equal NP would be too close-minded of us. Although quantum computers, like classical computers, are not currently believed to be able to solve NP-complete problems in polynomial time, with the world’s best minds constantly in search of new answers and new ways to solve problems, I don’t think it’s unrealistic to say that someday in the future it could be proved the P does in fact = NP.
What do you think?
- Najdah G
"I know an NP-Complete joke, but once you've heard one you've heard them all."
SOURCES