So, it looks like intractable problems are something that we're going to have to live with, so let's talk about different approaches. So, first of all, we're saying when you encounter an NP complete problem, it's pretty safe to assume that's intractable. So, what should you do? Well, I'll talk about at least four approaches that are successful. The first and most important is don't try to solve it. You have to know what you're doing. Very unlikely to find a guarantee problem real-time algorithm for your problem. But one thing that you can do is, take a look at the inputs, the types of incidences that you have, and remember that this whole theory is talking about the worst case. It's talking about guaranteeing that you have polynomial time in all inputs. Maybe the ones that you have to solve in the real world are not the hard ones. Another thing to do is to look for not complete solutions. The best traveling salesman tour but one that's close to the best. I'm not going to talk much about that but there's been a lot of emphasis on that and the other thing is to just take advantage of the idea of intractability and I will give an example of that. So, don't try to solve intractable problems and these are cartoons from the Gary and Johnson book on intractability. That was the first to really just after a car within not many years after carp to formulate hundreds and hundreds of these problems and develop the theory. And this cartoon is from the book. So, if you're somebody that knows no theory and your boss says, I've got salesmen, go get me the optimal tour, all you could do is say, well, I can't find an efficient algorithm. I guess I'm just to dumb. Note The spelling of to. So, that's where you'd be pretty stuck with your boss. Now if you know about Turing and computability and the boss asks you to write a program that takes any programmers input and tells whether it halts. You can say, I can't find an algorithm because there's actually no algorithm possible and I can prove that to you and you're the one that's too dumb. But now with intractability, what you can say is, well, I can't find an efficient algorithm but neither can all of these famous people. So, you're in pretty good ground as long as you understand when you're facing intractability. Well, here's an important example from a scientific field statistical physics and this is just a sketch but it's something that's going on all over science, since the importance of this theory has been recognized. So, there's the Icing model for ferromagnetism. A mathematical model in the 1930s, the field of statistical mechanics, important research direction was developing a closed form solution to this model. And in '44 there was an amazing paper that impressed people working in this field, there was a closed form solution to the two dimensional version of this problem. So, spurred on by that success, Richard Feynman and many others many and very accomplished scientists were seeking for many years a closed form solution to the 3D version, which is of course the one that we have to cope with in the real world. But around 2000, in which researchers showed that this problem is NP complete. Which meant that, all that effort for 50 years was really kind of wasted. If those people had known about intractability, they would know not to try to find a closed form solution or at least do it with the understanding that it would be the scientific breakthrough of the century. So, work on another problem or work hard and I'm just proving that P equals NP. Maybe this is the way to show that P equals NP but least ought to know that. And again, thousands and thousands and thousands of problems are in this category, and you don't want to be the situation of beating your head against a brick wall for 50 years trying to solve a problem that we know is very unlikely to have an efficient solution. So, again one thing we can do that I mention is that in practice you might not have these worst case inputs so, it might be that there's some inputs, a small number of inputs that cause an algorithm to take exponential time, so therefore, you can't guarantee that it will run in polynomial time but the ones say you have to solve might be easier. So, a reasonable approach is to say just take away the condition that it has to work on all inputs. Maybe it's enough that it works on the inputs that we care about. And there's lots of examples of this. This is a very fruitful way to look at the situation. So there is a program that solves 10,000 variable instances of SAT. Now these things are not running in time proportional to two to the 10,000. They're fast polynomial time algorithms. This is actually developed by an undergraduate independent worker in 2000 and the joke is that if you've got a large SAT instance you can tell the difference between a theoretician and a practitioner. Practitioners say, if I can make my problem into a SAT instance, then I can solve it using a thing like this. Whereas a theoretician would say, if all you can do is get it to SAT, you have to give up because SAT's intractable. Even traveling salesman problem. People have this program called Concorde that routinely solves huge real world instances and they did ten years ago. They we're doing 80,000 city instance and it's much higher now. And even integer linear programming, the CPLEX which routinely solves huge real world instances for big corporations, solving problems that they need in order to get their work done. And also many scientific applications. So living with intractability is certainly a fruitful approach and worthy of a lot further study. And then there is exploiting intractability and certainly the famous example of that is the RSA cryptosystem. So, you don't have to sell cryptography nowadays. Everywhere on the web cryptography plays an important role because financial transactions depend for their security on secure communications and good cryptography. And there's a very long list of the applications. The RSA cryptosystem which was developed at MIT in the 70s is a method that exploits the intractability, the difficulty of factoring. So, to use it what you do is multiply and divide two long integers and that's relatively easy. That's polynomial time and the number of digits in the integers. But to break the system, you have to be able to factor a long integer we actually don't even know if that's intractable. There's no reduction from SAT and I'll talk about that in a minute but it certainly seems difficult. So, multiplication is easy. Factoring is difficult. So for example, go ahead try to write a program to factor this 212 digit integer. And Rivest, Shamir and Adleman offered a prize for this. Now, it's a little bit outside our theory because there's no reduction from SAT known. So, efficient algorithm for a factor would be would break the cryptosystem but it wouldn't prove that P equals NP so you can say factors not known to be complete. Could be that we just don't know the reduction but it's pretty safe to assume that it's difficult or even intractable. It's not as safe as the assumption is for an empty complete problem. If you solve a FACTOR you just solve FACTOR. You don't prove the P equal NP, you don't solve all those other problems. But still, that's a good example of exploiting the difficulty of a problem. So, what are RSA actually wound up doing was creating an e-commerce company that actually was worth billions, really based on this idea from theoretical computer science. There's actually a price now for resolving P equals NP since 2000. You'd get a million dollars if you resolve P equals NP. You probably win a Turing Award nowadays and get another million dollars. So, theoretical computer science definitely can make you some money. And by the way, if you broke P equals NP maybe you wouldn't want to claim the money because you would break e-commerce or you can sell t-shirts is another way to go. So, just one final thought and it's important question nowadays. So, we talked about the difficulty of factoring and the idea of can we assume that it's intractable? Well, maybe we could but there's something else that has come up. It seems like we've made the simplest assumptions that we possibly could but in the mid 1990's Peter Shor proved that, there's a method for factoring an N bit integer in just N cube steps polynomial time on a device known as a quantum computer. Quantum computing, is something that many people have heard of. You can argue whether it's a reasonable model of computation or not, but you have to think about whether you still believe in the extended Church Turning thesis nowadays. The one that says that, resources used by all reasonable machines are within a polynomial factor of one another. If a quantum computer can be built and exist then that would falsify this thesis. But whether or not this happens, I think the important finishing point for this lecture is that intractability is something that we need to understand. It might even tell us something about the universe in which we live.
