P vs NP problem

In this episode I’ll discuss one of the most important problems in computing: the P versus NP problem. This is one of the seven Millennium Prize Problems, unsolved challenges in mathematics. 

The P vs NP problem concerns the field of computational complexity, a domain where theoretical computer science and maths regularly work together, and, in essence, it asks whether problems that have easily verifiable solutions also have reasonably fast ways to find these solutions. The answer to the problem has huge consequences for the limits of computer science, as well as the nature of creative genius itself.

https://whatwedontknow.buzzsprout.com/

Transcript

Hello everyone, welcome to the sixth episode of ‘What We Don’t Know’, a podcast that explores the boundaries of human knowledge, investigating the unanswered questions and theories that unravel them at the frontiers of science. During this podcast I hope to get you interested in new areas of science, maths and technology, teaching you about existing concepts and igniting a curiosity for the things we have yet to know.

    In this episode I’ll discuss one of the most important problems in computing: the P versus NP problem. This is one of the seven Millennium Prize Problems, unsolved challenges in mathematics, whose utmost importance is reflected in the one million dollar prize money associated with a solution. Of these seven, only one - the Poincaré conjecture - has a universally accepted proof. The P vs NP problem is the most recent Millennium Prize problem and also the easiest to explain, although I’ll explore others, like the Riemann Hypothesis, in later episodes. 

    The P vs NP problem concerns the field of computational complexity, a domain where theoretical computer science and maths regularly work together, and, in essence, it asks whether problems that have easily verifiable solutions also have reasonably fast ways to find these solutions. There seems to be a distinction between checking the solution to a problem, determining whether it’s valid, and having a method to find the proof yourself, and the P vs NP problem asks whether this distinction is as absolute as it seems. The answer to the problem has huge consequences for the limits of computer science, as well as the nature of creative genius itself.

    First, I will explain what computational complexity really is, why it’s relevant, and explain the different classes of complexity. Then we’ll take a closer look at NP problems. After giving some examples, we’ll dissect the P vs NP problem itself and consider the ramifications of a solution on a multitude of fields.

    So, what is computational complexity? The definition given by Britannica is ‘a measure of the amount of computing resources (e.g. time and space) that a particular algorithm consumes when it runs’. Something big and complicated will take longer to deliver a solution. It will probably use more memory. Time complexity can be expressed using big O notation, which describes algorithmic efficiency, or how time scales with respect to some input variables. For example, O(N) is how time scales with respect to N. Does it increase linearly as the problem gets bigger? Or does it shoot up to unattainable heights?

    This brings us to the classes of computational complexity, the ways of categorising problems in terms of how the associated program’s resource use scales up as the problem scales up. When I say ‘scaling’ I mean the increase from a 3 by 3 by 3 rubix cube to 5 by 5 by 5, to 16 by 16 by 16, and so on, or a similar increase in the width and height of a sudoku grid. 

    Set P is the set of all problems solvable in polynomial time. O(N) is a polynomial function, consisting of a list of variables, N, that are connected using only the basic operations of addition, subtraction, multiplication, and powers of non-negative integers, like N squared. All these problems can be solved reasonably quickly, no matter how big N gets. The easiest examples of P problems are polynomial calculations like 128 to the power of 5, plus 34 to the power of 72, times 4 cubed, etc, but puzzles are more interesting, and a rubix cube is a great example of a problem in set P: bigger cubes need more computing power, but are still solvable. Note that complexity usually considers the worst case scenario for a required number of steps.

    Outside set P is set EXP, which includes all the problems solvable in exponential time, as well as set P. The time (i.e. number of steps) required for a problem in EXP could be 3 to the power of a variable. As the variable gets bigger, computers will quickly be unable to handle the required resources. Chess with a grid N by N size is a classic example of an EXP problem. To find the best move, you could try all the possibilities, but that’s going to take a long, long time. 

    Then you have set R which encircles EXP. R includes all the problems solvable in finite time, i.e. solvable problems. The halting problem, which asks, given a computer program, does it ever stop running? is unsolvable. There’s a very neat proof for why there are many more problems outside R than there are inside R. 

    Firstly, you can convert any problem into a decision problem, which gives a yes or no answer. On one side is the program, which, no matter the language, is read by the computer as a sequence of ones and zeros, so can be thought of as a binary string, which can be translated into a natural number. On the other side is the decision problem, a function which takes an input, which is also a binary string and thus a natural number, and outputs yes or no. You can write the function as a table mapping all inputs to their outputs. Since the number of possible inputs is infinite, the function is an infinite string of bits. Putting a binary point (like a decimal point but for binary) at the start of this infinite string converts it to a real number between 0 and 1. Therefore, all programs are part of the natural number set, which is countably infinite, and all decision problems are part of the real number set, which is uncountably infinite. The real number set is far bigger than that of natural numbers, so only a tiny fraction of conceivable problems will have a corresponding program, and almost every problem is unsolvable - that is, not part of set P.

    Okay, but what about NP? The complexity class NP is within EXP but bigger than P, and stands for ‘nondeterministic polynomial’ time. NP contains decision problems solvable in polynomial time via a ‘lucky’ algorithm, where a ‘lucky’ algorithm is an algorithm that makes guesses then concludes ‘yes’ or ‘no’, but guesses are guaranteed to lead to ‘yes’ if possible, which means the algorithm will always give the correct answer with the first guess. Take tetris. Any choice you make in tetris - rotating shapes, where they drop - can be a guess. Ask the program ‘did I survive?’ and the NP program will lead guesses - playing moves - to ‘yes’. This sounds wonderfully far-fetched. 

    Another, nicer way to think about NP is that it contains decision problems with solutions that can be checked in polynomial time. In tetris, you play the moves that the program suggests and check if you survive. In sudoku, another NP problem, you check the combinations of numbers in the grid. There’s no efficient way to solve a 150 by 150 sudoku - that we know of - but it doesn’t take too long to check if one is valid if it’s already filled in.

    Before giving some more fun examples, a few more definitions. NP-hard is the set of all problems at least as hard as any NP problem. Adding -hard at the end of any class name has the same effect. Something is NP-complete if it’s both NP-hard and part of NP. Most of the best puzzles are part of NP-complete: minesweeper, RushHour, spider solitaire, battleship. Other problems include the travelling salesman problem, 3D shortest paths, finding the longest common subsequence for n strings, the knapsack problem.

    NP-complete becomes even more interesting when you consider reductions. A reduction is when you convert problem A, which you cannot solve, into problem B, which you can solve, for example converting an unweighted shortest paths problem into a weighted shortest paths problem by setting weights to one. 

    Reduction showed that Tetris was part of NP-hard because 3-partition is part of NP-hard and 3-partition can be reduced to Tetris. If Tetris could be solved in polynomial time, a similar method could be applied to 3-partition, making it also solvable in polynomial time. Since there’s rigorous proof that 3-partition is NP-hard, Tetris must be NP-hard too. In fact, all NP-complete problems can be reduced to each other! They all contain a uniting core problem, and it’s this that prevents any algorithm from finding a solution, even though solutions can be easily checked.

    The big question, the golden ticket, the P vs NP problem itself… Does NP equal P?

    If a problem allows quick verification, can it also be solved quickly?

    If all NP problems are indeed part of P, many problems will suddenly be in the realm of the possible. This is not just about enormous sudokus. NP problems include analysis of protein folding, forecasting financial markets, and mathematical conundrums upon which modern cryptography is founded. If NP equals P, finding the way in which chains of proteins fold into 3D structures, which affects everything in cells, will be possible using programs. If NP equals P, people will be able to efficiently factor huge composite numbers, eroding the base of cryptographic security. 

    But, if NP does not equal P, the problem-solving power of computers will remain fundamentally and permanently limited. In reality, proving that P does not equal NP will not affect much, since most people believe that to be the case. Programmers prioritise reformulating NP problems into something more computable, because that’s more effective. People are good at finding workarounds. 

    Moreover, proving one side of the P vs NP problem is so hard because proving things is an NP problem. So P vs NP is part of NP! 

    Ultimately, the P vs NP problem asks whether generating solutions is significantly harder than checking them. Work on this problem has huge ripple effects across computer science, mathematics, medicine, economics and more. 

    It also questions the very nature of human creativity. Scott Aaronson, a computational complexity specialist at MIT, said that if P equals NP, “the world would be a profoundly different place”. There’d be “no special value in ‘creative leaps’, no fundamental gap between solving a problem and recognising the solution once it’s found. Everyone who could appreciate a symphony would be Mozart.” End quote.

    As always, it’s a tough problem to crack.

    Thank you for listening.