--- Video Title: History of the Cook-Levin Theorem Description: Theory of Computation https://uvatoc.github.io/week11 25.4 History of the Cook-Levin Theorem - Cook's Original Paper - Primes Problem - Levin's Original Paper - Universal Search Problems David Evans and Nathan Brunelle University of Virginia --- I'm going to do a little historical excursion on the Cook-Levin theorem. There's an interesting story behind it. Often theorems that are named after two people, often the assumption is, well, they work together. So this one, totally independent. So this is Stephen Cook, who is the cook in Cook-Levin. Some people do still call it Cook's theorem. And he came up with this early in his career. He was a professor at Berkeley in the math department and was denied tenure. So went to Toronto. They were not convinced that working on these kinds of computing questions was actually interesting. If math was smart, they would have taken over computer science by thinking this was interesting and worthwhile. Instead, they basically kicked him out. And this is a paper. And it's actually quite readable. It's only about five pages long. And you should be able to understand pretty much everything in it. So if you blow up the abstract, this is what it says. It is shown that any recognition problem solved by a polynomial time-bounded non-deterministic Turing machine. That's exactly what we've been talking about, non-deterministic term machines that run in polynomial time, can be reduced. So back in 1971, if you used reduced in a paper, you had to put it in quotes, because it was not an accepted thing, what reductions meant. So he's introducing what a reduction is. But what he reduces it to is determining whether a formula is a tautology. We'll get to, in a couple of slides, what that actually means. But this is different from what we said the Cook-Levin theorem was 3-STAT. That's not what we're calling the Cook-Levin theorem now. Now explain what reduced means. That we can solve one problem using the other one. So that's actually the first two sentences of the paper right there. So this is the theorem, which corresponds to what we've been talking about as the Cook-Levin theorem. It says if there's a set of strings accepted by some non-deterministic Turing machine within polynomial time, this is basically saying S is in NP. Then we can reduce S to this problem. What's another way of saying what this theorem is saying, now that you've got the terminology we have? Our definition of NP-hard is every problem in NP can be reduced to that one in polynomial time. Basically saying this tautologist's problem is NP-hard. So we use CNF to show 3-STAT. CNF was conjunctive normal form, which is ORs connected by ANDs. DNF is ANDs connected by ORs. Switching the ANDs and ORs around, tautology is there's no way to make it false versus satisfiability is there's some way to make it true. So that's how the problem is similar, but it's actually sort of the complement of 3-STAT. To know that there's no way to make it false, we've got to know that all possible ways of assigning those variables lead to one of those clauses being true. For satisfiability, we've got to say that we can find some way of assigning those variables that leads to all of those clauses being true. This is kind of the part of it that's basically showing it seems like this is an interesting thing to do. At the time that Cook did this, people didn't know what NP was. There wasn't a class NP. People weren't saying, oh, it's obviously interesting to show something is NP-hard. So he said, well, here's some problems that are polynomially time-reducible to this DNF tautologies problem. Do we recognize any of those problems? These are graph ones. Graph isomorphism is definitely a famous NP-complete problem. We haven't talked about it in class. This one is actually DNF tautologies. So that's kind of uninteresting that you can reduce it to itself. That's almost cheating to count that one. And this one is sort of a variation on that. So it wasn't the most interesting list of problems, although there's one pretty surprising one on there. The set of prime numbers. So he's talking about sets of strings. What is primes as a function? So remember, our functions should be things that take in x is some string of bits. What does the function prime do that's corresponding to that primes? So it is a test whether the input is prime or not. It should turn one for any input that's prime. So this is one that's pretty surprising on his list. Is there an obvious polynomial time witness to prime? If a number is prime, is there an easy way to prove that it's prime? If it's not prime, is there an easy way to prove that it's not prime? Yeah. So give the fact. Give two numbers that multiply to it to do that. I think this is a little bit surprising. It was unknown until 2002 whether primes was in p. But there actually was a result about 17 years ago now that showed there is an algorithm that does decide prime in time that scales as n to the 12th. Pretty big polynomial. They actually got it down to n to the 6th. But definitely within p. And it was actually started as an undergraduate thesis project. These two students at IIT showed that there is a deterministic polynomial time algorithm that decides prime. Does this mean Cook was wrong? Maybe Berkeley was right to kick him out? Yeah. No? Good. Yeah. If he claimed that primes was NP-complete or NP-hard, that's definitely wrong. It would be either wrong or the fact that primes is NP would say P equals NP. And we know that did not say that. Finding the polynomial time for primes. Because there's no reduction from DNF tautologies to primes, what he was claiming is the reduction in the other direction. That we can use DNF tautologies to solve primes. And the fact that primes is NP says, well, that would be a silly way to solve primes. Because we know a fast algorithm to solve primes. That's the important thing about the direction of the reduction. Thinking of it in terms of which problem is harder. So what about Levin? So we've only been talking about Cook. Why is it named the Cook-Levin theorem? And there's a little hint outside Alderman Library. This was done in the late 60s, early 70s, when the Soviet Union and the US kind of had their own theoretical computing communities. There was a pretty big Cold War. There was a wall in Berlin. There was a lot of work going on in places and ways that was not visible to each other. So Levin independently came up with this from a very different perspective. So who reads Russian? You can probably actually read this if you know your Cyrillic alphabet. This is universal search problems. That kind of almost transliterates if you can turn the Cyrillic alphabet. Without knowing Russian, those words actually sound pretty similar. I think Y is like a U and this is definitely a P. So universal search problems. Why was he talking about universal search problems? Is that related to this? All the NPQ complete problems are kind of problems where it seems like you have to do a brute force search. And they're all similar in the sense that you're searching for some input that has some property like the longest path or like the variable assignment that satisfies that formula where you're searching and you're searching without enough structure to make that search efficient. So that's where the notion that these are universal search problems. And there was a Russian name for this that was kind of like brute force search problems. If we know that they're brute force search, that there's no way to find enough structure to make that search more efficient, that suggests that there's never going to be a polynomial time solution. And even in the late 50s, there were people that kind of had that intuition that there were problems like this. Levin was the one that formalized it. And what he did in this paper is describe six problems. So we saw in Cook's paper, there was this list of six problems, but they were really only three substantially different ones. If you don't read Russian, there is a translation of these problems. The problems here, there are two that are really similar to the ones Cook wrote about were the graph isomorphism problems, telling if two graphs have the same structure. The one that's problem number three... Do you recognize problem number three? It's really... not exactly the same, but it's really close to a problem you have seen. So the formula here, this is a logical formula. The or equivalently part is a lot easier. Kind of like satisfiability. Some property of a formula, it's not exactly the same as satisfiability, but you could see that maybe it's similar enough that it's not surprising to be on this list. The point now has to follow effective versions of two parts in an recipe video and that when results are in a설seyed prompt, We'll see where the thing happened next questions of two parts. We'll see. How could we go on the back of 15? However, we can keep it everywhere.