Biggest Puzzle in Computer Science: P vs. NP
Quanta Magazine
https://www.youtube.com/watch?v=pQsdygaYcE4

Transkript (automatisch erstellt)

0:00 Is it possible to invent a computer that computes anything in a flash? Or do problems exist that would stump even the most powerful computers imaginable?
0:10 How complex is too complex for computation? These questions are central to a fascinating conundrum
0:17 called the P versus NP problem. P versus NP,
0:21 is one of the great unsolved problems in all of math and computer science, or, you know, really in all of human knowledge, if we're being honest.
0:30 Anyone who finds a solution could win a handsome $1 million prize offered by the Clay Institute.
0:37 And this solution could lead to breakthroughs in everything from medicine to artificial intelligence,
0:42 and even the perfect game of Mario Brothers. But it would come at a cost.
0:47 A definitive answer to the P versus NP problem could break your bank account and even lead to the end of the internet as we know it.
0:57 To find out why, let's start with a simple logic puzzle. A robot arrives in a foreign land where everyone either always tells the truth
1:06 or always lies. The robot reaches a fork in the road with two choices.
1:11 One path leads to safety in the land of truth tellers, while the other leads to doom. In the land of liars.
1:18 A sentry appears. But it's unclear which group they belong to.
1:22 What question can the robot ask to determine the safe route? Here's some options...
1:31 And here's the answer. With this one question,
1:36 both types of sentries would point to the correct safe path, allowing the robot to solve the problem quickly.
1:42 Now, what if the robot encounters multiple sentries and dozens of pathways leading who knows where?
1:48 What can it do to find safe passage? Compared to the first problem,
1:53 is a correct solution here proportionately more difficult to find? Or is it exponentially harder?
1:59 Maybe there's a shortcut that could speed things up? Or maybe finding a solution to this complex situation is nearly impossible.
2:09 The question of how hard a problem is to solve lies at the very heart of an important field of computer science called computational complexity.
2:17 Computational complexity is the study of the inherent resources such as time and space that are needed to solve
2:26 computational problems, such as factoring numbers, for example. And especially it's the study of how those resources scale
2:34 as the problems get bigger and bigger. Computational complexity theorists want to know which problems are solvable using clever algorithms.
2:42 And which problems are truly difficult, maybe even practically impossible for computers to crack.
2:48 So how do computers solve problems in the first place? A computer's core function is to compute.
2:56 These machines perform basic mathematical operations like addition and multiplication faster than any human.
3:03 In 1936, a 23-year-old British University student, Alan Turing, developed a fundamental theory of computation.
3:11 While attempting to solve a problem about the foundations of math, Turing claimed in a paper,
3:16 it's possible to invent a machine which can compute any computable sequence given enough time and memory.
3:22 This simple, theoretical Turing machine, which includes a place to store information
3:27 and a device to read and write new information based on a set of instructions,
3:31 is the basic framework for all digital computers to come. One of the key insights of computer science is that Turing machines are
3:40 mathematically equivalent to just about any other programming formalism that anyone has invented,
3:47 at least for conventional computers. Inside a digital computer, data are represented as binary bits,
3:54 sequences of ones and zeros. And these bits can be manipulated through logical operations
3:59 using a branch of math that preceded the invention of computers called Boolean algebra.
4:06 The basic rules of Boolean algebra were formulated in 1847 by English mathematician, George Boole.
4:13 Boolean algebra formulates decision problems, yes or no problems that can be asked in sequence to answer complicated questions.
4:21 The output of a Boolean function for any given input can be represented in what's called a truth table, and it is either one or zero.
4:30 True or false. Expressions in Boolean logic consist of multiple variables linked together by
4:37 three logic gates: AND
4:39 OR NOT.
4:42 These logic gates work like this. For an AND gate, when the inputs for both variables X and Y are true,
4:50 the expression evaluates to true otherwise it's false. With the OR gate,
4:56 the expression evaluates to true when either X or Y is true. A NOT gate simply inverts the value of a variable,
5:04 switching a true to false or vice versa. By using only these three simple,
5:10 logical operations and building them up into various configurations, Boolean formulas can operate like a Turing machine and theoretically solve any
5:18 computable problem. In 1937,
5:22 an electrical engineering graduate student, Claude Shannon, demonstrated in his master's thesis that the Boolean operations AND, OR,
5:30 and NOT can be calculated using electronic switching circuits. A decade later,
5:35 Bell Labs introduced the first solid state semiconducting transistor. Transistors are simple, electronically controlled switches with three wires,
5:45 a control wire, and two electrodes to input and output data. They can be in one of two states, on or off,
5:52 representing either a one or zero. True or false. Transistors can be combined and arranged in different configurations
6:00 to mimic the Boolean logic gates of AND OR, and NOT. By combining enough of these transistors together
6:07 on computer chips in complex arrangements called circuits, it's theoretically possible to compute almost anything,
6:14 anything that is computable, that is, More about that later.
6:19 In the 1950s, Hungarian American mathematician and computer scientist, John von Neumann brought the modern computer
6:26 one step closer to reality. He developed the architecture of the universal electronic computer,
6:32 the same architecture at work inside most electronic computing devices today, from smartphones to supercomputers.
6:39 Since the mid 1950s when the first transistor based electronic computers were built, the technology has swiftly advanced.
6:47 by scaling down and cramming more and more transistors onto tiny chips, computing power and speed has nearly doubled every two years.
6:55 Today, computers can perform trillions of calculations per second. But even that's not always good enough.
7:02 There's a class of problems that computers can never solve. A quandary Alan Turing foresaw in the same paper where he conjured up his
7:09 calculating machine. Turing had the insight and in fact proved that not everything is computable.
7:16 The limiting factor is not the hardware, but instead the software or program. Computers solve problems by followinglists of instructions called algorithms.
7:27 An algorithm just means a step-by-step procedure for solving a problem. Running an algorithm is analogous to following the steps of a recipe
7:36 or an IKEA assembly manual. Here's an example of an algorithm that sorts a list of numbers from lowest to highest.
7:43 It works like this. Take a random list of numbers.
7:47 Start with a first number from the left, which here is six. Now look through the remaining numbers and identify the smallest one,
7:55 which in this case is three. Next, swap the places of six and three,
7:59 and you'll have the smallest number in the group on the left. Take a second pass this time,
8:04 starting with the second number from the left. Swap with the smallest and so on.
8:11 After enough passes, all the numbers are sorted, lowest to highest using this simple algorithm.
8:18 Any problem that can be solved by an algorithm is computable. But by the 1970s, computer scientists realize that not all computable problems
8:26 are created equal. Some turned out to be easy,
8:30 while others seemed hard. For problems like multiplication,
8:34 computer scientists found really fast algorithms, but for others, like optimizing the operations in a factory,
8:40 they couldn't find any easy solutions. And it turned out that some problems were so hard,
8:46 the only known way to solve them could end up taking more solution steps than there are subatomic particles in the universe.
8:53 Thus, the P versus NP problem was born. So what exactly does P and NP mean?
9:02 P problems, or problems that can be solved in polynomial time are the types of problems that are relatively easy for computers to solve.
9:09 The vast majority of what we use our computers for on a day-to-day basis, you know, you could think of as solving various problems in P.
9:18 From finding the shortest path between two points on a map. to sorting a list of names alphabetically,
9:24 or searching for an item on a list. These are all examples of polynomial P problems.
9:30 A polynomial is a mathematical function that can contain variables raised to a fixed power or exponent
9:37 like N to the power of two or n cubed. The time it takes a computer to solve P problems grows polynomially
9:44 as the input increases in size. Given enough computing power,
9:49 all problems in P can be solved by a computer in a practical amount of time. Now, NP problems are a class of problems that share a unique feature.
10:01 If given the solution, it turns out to be quick and easy to verify If it's correct. Easily solved P problems are contained within the class of all NP problems
10:11 because they can also be verified relatively quickly in polynomial time. However, there's a class of NP problems that are easy to check,
10:20 yet seem difficult to solve in the first place. It's really helpful to think about something like a jigsaw puzzle or a Sudoku puzzle, right?
10:29 We all have experience that, you know, these could require an enormous amount of trial and error to solve.
10:35 But nevertheless, you know, if someone says that they solved it, it's much easier to check whether they did.
10:41 If someone gives you a completed hard puzzle like a large Sudoku or crossword, the answers can be verified much fasterthan it can be solved in the first place.
10:49 It's the same for a computer. The reason these types of NP problems can be more difficult
10:55 for a computer to solve is because as far as we know, their complexity increases exponentially as their input increases.
11:04 An exponential function has the variable in the exponent like two to the power of N. Here's an example of exponential versus polynomial growth.
11:13 For the same input. With these hard, exponential NP problems,
11:18 the increased complexity of large inputs can quickly exceed the limits of what a computer can compute in a reasonable amount of time.
11:25 And solving them using brute force techniques alone is practically impossible. You could be doing that, you know,
11:32 from from now until the whole universe has degenerated into black holes and you wouldn't have even made a dent in it.
11:40 Over the years, mathematicians discovered clever polynomial algorithms for some seemingly
11:44 difficult NP problems. Proving that these problems were actually in the simpler class P
11:50 and making them solvable by a computer. This opened the door to the question,
11:56 are all NP problems really P problems? Could every problem that is seemingly intractable for a computer to solve today
12:03 turn out to be easy in the future? P equaling NP would have far ranging consequences.
12:10 Solutions to nearly any problem would be well within our reach. AI would become smarter overnight.
12:17 Businesses could solve complicated optimization and logistics problems boosting the global economy.
12:23 And scientists could make once unthinkable breakthroughs. Maybe we could even find a cure for the common cold?
12:31 However, if P equals NP, that would also mean that all current methods for strong encryption
12:38 security measures that protect everything from your online privacy to your crypto wallet
12:42 would instantly become obsolete. It would be hacker heaven.
12:48 In the 1970s, mathematicians Stephen Cook and Leonid Levin
12:52 working independently on opposite sides of the Iron Curtain, made important discoveries that have come to define the P versus NP problem.
13:01 They discovered the idea of NP Completeness. Almost all of the notoriously difficult problems in NP are actually equivalent.
13:10 So if you could prove one of those is equal to P, you've solved all of P versus NP.
13:18 This is kind of like a veterinarian realizing that even though toy poodles and St. Bernard's look very different,
13:24 they're in fact the same species and a treatment that works on one would very well work on the other.
13:31 There are hundreds of known NP Complete problems, and finding a single solution would lead to breakthroughs on multiple fronts,
13:39 including physics, economics, and biology. Not to mention computer science itself.
13:46 NP Complete problems include a host of famous problems you may have heard of, including the Knapsack Problem,
13:51 which involves the most efficient way to pack items like in a suitcase. Or the Traveling Salesman problem, which involves route planning and navigation.
14:01 Complicated NP Complete problems, even underlie everyday tasks
14:05 like figuring out how to deliver millions of Amazon packages on time or efficient in life-saving matching of organ donors with recipients,
14:13 and even mastering games like Tetris or Candy Crush, All known NP Complete problems can be transformed into one another.
14:23 The most famous of these is what's called the Boolean Satisfiability problem, or SAT.
14:28 SAT is one of the most famous problems in computer science. Besides its theoretical interest,
14:34 it's a very fundamental workhorse problem in applied computer science, especially in software verification.
14:42 SAT is a decision problem that asks: for a given Boolean formula or
14:46 expression made up of N variables and the logical operators AND, OR, and NOT.
14:52 Is there a combination of true-false variable assignments for which the entire formula evaluates to true?
14:59 If so, then it is said to be satisfiable.
15:03 If someone can devise a clever fast algorithm for the SAT problem making it easy to compute, then voila! Proof that P equals NP.
15:14 However, most computer science researchers believe that P doesn't equal NP. And proving P doesn't equal NP has turned out to be one of the hardest problems
15:24 in math and computer science. In the 1980s,
15:29 one promising avenue of research emerged called circuit complexity. The field studies the complexity of Boolean functions when represented as circuits.
15:38 The behavior of any given Boolean function can be described by its truth table. However, the same truth table can be produced by circuits of differing complexity
15:48 as seen in these two examples. A Boolean function's circuit complexity
15:53 is defined as the total number of logic gates in the smallest circuit, which can compute that function.
15:59 Researchers study circuit complexity to understand the limits of computation and to optimize the design of algorithms and hardware.
16:08 For some Boolean functions, the minimum number of logic gates grows polynomially
16:13 as the number of input variables increases. These are said to have low circuit complexity
16:18 and are analogous to P-class computational problems. Functions where the number of necessary logic gates grows exponentially with
16:27 increasing input variables are said to have high circuit complexity.
16:32 One potential approach for proving P doesn't equal NP required researchers to identify a single function known to be in the class of NP,
16:41 that's also definitely has high circuit complexity. In 1949, Claude Shannon proved that most Boolean functions have high circuit complexity.
16:51 So how hard could it be to find one instance? Harder than it sounds.
16:57 Alas researchers encountered a mathematical roadblock called the Natural Proofs Barrier.
17:03 This barrier implies that any proof that P doesn't equal NP using known circuit complexity techniques would have to have a bizarre and self-defeating character.
17:13 Clearly, a different way forward was needed. While most researchers started looking for other approaches,
17:20 some began to investigate the Natural Proofs Barrier itself, leading them to new questions.
17:26 How hard is it to determine the hardness of various computational problems? And why is it hard to determine how hard it is?
17:33 It's a very meta area of computer science called meta-complexity. It has turned out that a lot of the progress that one can make on
17:43 problems like the P versus NP problem today, you know, involves sort of self-referential,
17:51 arguments, involves sort of turning inward. Given the limits of known techniques,
17:55 meta-complexity researchers are searching for new approaches to solve some of the most important
18:00 unanswered questions in computer science. And crucially meta-complexity is intimately connected
18:06 to the question of whether provably secure cryptography schemes even exist. One important current focus of research is what's called the Minimum Circuit
18:17 Size Problem, or MCSP. MCSP is interested in determining the smallest possible circuit that can
18:24 accurately compute a given Boolean function. Is there a simple solution?
18:29 The Minimum Circuit Size Problem is a problem about circuit complexity, but how complex is the problem itself?
18:36 Researchers suspect that MCSP is NP complete, but unlike many other similar problems, they haven't been able to prove it.
18:45 A proof of MCSP's NP-completeness would be a big step towards showing that secure cryptography does exist.
18:54 And recently there's been tantalizing progress towards that goal. Like the robot searching for safe passage in a foreign land,
19:02 the pursuit of meta-complexity is blazing a trail for theoretical computer science. A path that may lead to an answer to whether P equals NP or not.
19:12 If civilization lasts long enough, you know, I would tend to think that probably problems like P versus NP will
19:20 someday be solved, and my main uncertainty is, is it humans who solve them or is it AI?
19:27 Is it GPT 10 that solves the P versus NP problem for us?
19:32 And then will we be able to understand the solution if it does?