# Beyond Computation: The P versus NP question (panel discussion)

Jun 08, 2021
The way we will proceed is this: first I will give extremely brief presentations to all

#### panel

members, then the

#### panel

members will in turn vent whatever they want to say about the P versus NP issue and related things.

### question

s, we'll spend about 20 to 25 minutes on the wisdom of the panel, and then I'll move on to the

### question

s posed by the audience and I'll ask the panelists to respond to those questions, the first panelist to speak will be uh Christos papad Demetrio and I'm going to being ruthless by subjecting each panelist to a three minute limit, you said 25, that makes it 20, 25 for you, no, I think dick was C, so calculus is an extremely practical and mundane thing, so It must be interesting because of that, okay, and frankly, I don't think so, okay, you know, the reason why this is an interesting question, I think it's much more basic, there are some questions that you can't, you don't dare to call important, I mean, know how.
Is there a single equation for what governs the cosmos? Is there the origin of how life began on Earth? Okay, so you know, if you want to argue that these questions aren't important, I don't want to argue. with you, okay, so, um, and I think, uh, P versus NP is, you know, exhaustive search can always be expanded. Okay, how can you not try to answer this? How is it possible that you don't want to respond? Know the answer to this question. Do you know if? If we manage to live on this planet for a couple more thousand years, I mean, we know and we can't answer this question, I mean, we know what, you know what the point is, okay, so the other thing you know is?

## beyond computation the p versus np question panel discussion...

What does MP P versus MP and M mean in practice? Well, because many of you may know that there are practitioners who come and tell all of us and tell all of us that they know these complete M problems that I solve. them, you meet thousands of them every day, so you know my business depends on it. Well, then I solve them so that you see that people are very smart, very innovative, very versatile, and can essentially live with anything, including happy fulfillment. Well, you already know. They, they, uh, find ways to solve even extremely difficult problems.
It's true, I mean, you know, just so you know, the point is this: when a problem has been proven, then it will be complete, not that it will never be solved, it will be solved, okay, but you. you have to change the meaning of the solution to be able to solve it, do you know that the solution cannot be clean? cannot be satisfactory. Can't you tell when you prove that a problem is in P when you develop a polynomial time algorithm for a problem? That's really surprising, you know? So you've really done a good day's work, haven't you? uh, you know, there was a man named Jack Edmunds, who back in his day in the '60s found these incredible algorithms for some very, very complicated problems.
Well, polynomial time algorithms. I know for a fact that he was very satisfied that day. Well, you know, I know, I know. You know he slept very well that night. Well, you know, so, so, ultimately, P versus Andan is about peace of mind and a good night's sleep. Alright? I forgot to introduce Christos Christos is a long-time colleague at the University of California at Berkeley and has had a PhD at Princeton since 1976. Our next speaker is Om Reinold, who is at Microsoft's Mountain View Laboratory and received his Ph.D. at the Whitesman Institute. in Israel, so before we start just one sentence to complete Christos H, even if we don't solve a big problem, even if we don't solve it, we have a lot of things in the way and I think this is true for everyone. the other problems that Chris has mentioned and I think it's also true H for p versus NP and not only did we spend decades not solving it, um, but I want to state now that if I'm taking a physical kind of analogue when If we want to learn about hardness calculations

## computation

al and what is difficult, we need to see it at all ranges, from stars and galaxies to atoms and particles, and the questions further down are how hardness is formed, how it is formed.
How do things get difficult? Is there anything in the range between things we can't solve and things that are very easy? I'll try to give very quick examples that the first one is something called pricing by processing an idea. for 22 years for fighting spam, which I think can be found in things like Bitcoin and this is the point of being okay, what's the problem with spam? Spam is very effective because emails are very cheap, so if you send your email to 1 million people and only one of them responds to your Nigerian scam, this is still worth it, so maybe one approach is to make email to be a little more expensive and here's an idea: when I want to send an email to someone, in return I have to solve a very simple and simple problem, for example, a soku problem that happens to also be NP complete and now when I solve it with my email I will send the solution to the problem but now to use that idea we really need to understand the problem so we know that when soduku problems become very very big they are invisible it is very difficult to solve, we cannot solve them and where there are very young children we can solve them, then, in the middle is the weak point for that, we need a very good understanding and another thing that I do not know how I can do with the microphone, so when we have cards we know that every time we play with them we need to shuffle them in some way and we know that doing it once is not like that. pretty good, it still has a lot of structure, but if we do it I don't know seven times eight times, it's already good enough and we can know it for several other things as well, very simple kind of mixtures so we know exactly how many times. we have to do it to create something, okay, create something that is random enough.
Very similar ideas are useful in cryptography, but it's not about making things very random, but making it something difficult that can hide your messages and find them exactly. so, in the information theoretical sense, in the sense of randomness, it is very easy to know exactly. I can tell you that seven is a good number of mixes, really understanding what is the number of mixes that make things from very easy to very difficult, is exactly the type of problems that are solved. below we want to respond thank you thank you mayor our next speaker is Ryan Williams PhD from Carnegie melan and professor from Stanford University thank you so I want to talk a little bit about professor cser's comments on how to prove that P is different of MP things like that, so I want to say something that may be a bit of a controversial veral but it is true, so very few people, that I know, actually work on P versus NP and among those who do, almost all of them are a complete nutcases that I have no idea what they're doing okay including myself by the way okay and and why is this like that?
I want to make some comments to you about why, um, when is it that we are very far from understanding problems like P. versus NP understanding what can feasibly be done with computers and what can't be done. You saw this very large Vin diagram. Professor Zipser showed that much of that VIN diagram could collapse completely, as far as we know, as if exponential time calculations could be solved. polyal random time so that the RP class that the primality was in could solve everything in exponential time, so this thing could completely collapse or we think it's appropriate, we think there's a very nice Vin diagram to design, but we're really far from understanding that, to refer again to the professor's talk, uh sister, we have to really hit that computer to prove that it can't solve MP problems, we have to break its legs, its arms, its neck and you know, we have to do it. do some damage, um, yeah, so, for example, you could try to show that algorithms with very constrained memory have extremely constrained memory, like a memory so small, that they can't even store a partial solution, um to show that they can't solve MP problems like cleck, this is completely open ended above, this is called the log space vs MP question, but there are all these other questions that we still have no idea how to address, we don't really know step one and in We actually know why we don't do it.
I don't know, okay, so there are these no go theorems, they're the so-called barriers, what they're called um, which basically state that the common proof techniques that we know are some of the techniques from the theory of recursion, etc. they're just not strong enough to distinguish between things like P and NP or even much weaker questions than P versus NP and so not only can we not prove it, but we can prove that we can't prove it's right, so that this has led to a lot of pessimism in complexity theory, but I'm actually optimistic, okay, despite all that, I'm very optimistic, there are many new techniques that overcome these barriers, in fact, um B, and only at a very high level, what?
What they do is they show in a very abstract way how efficient computer programs for solving some tests can turn into impossibility results. P are not the same as NP type results to solve other tests, so we take advantage of a kind of human intuition and problem solving as skills that we have. it can actually show that other problems cannot be solved efficiently, so understanding them, the connection between them is very important, thank you, oh, you don't sound like a nutcase at all, next we have Russell and Patoo, a Ph.D. at Berkeley in 1992 and professor at UC.
San Diego, okay, the first thing I want to do is respectively disagree with Kristos on one point, which is that those of us who have failed to solve the P versus NP problem often go on to rich and rewarding lives of other ways, um and those. Those who don't can be classified as cranks. um, what P versus NP is a really fundamental issue, as all my colleagues have emphasized, what I want to continue to mention is that it's not really kind of the end goal of complexity theory. really the first step of complexity theory is a big step, but it is still the first step.
An example of where we would like to go next. It comes from some of the applications having difficult problems, like cryptography and security wherever you want. Having the toughness to solve search problems prevents hackers from misusing your system. Well, now there are two distinctions that need to go beyond showing that P is different from NP. P is different from NP means that there are difficult cases of these problems. Okay, but. it doesn't tell you which instances are actually difficult per se, it doesn't tell you how to craft hard instances or how to craft instances of a known difficulty like Omar was mentioning that he'd like for his spam filter, okay? that to try to get there we have to understand not only how hard NP problems are in the worst case, but how hard they are in different ways of making these hard problems, different probabilistic distributions, which is the subject of the theory of the average complexity of Levan cases, however, that is Even that is not the end because we have to be able to distinguish between legitimate users who should be able to solve our problems and attackers who should not be able to solve them, so what we need to basing security on hard problems is some notion of not just a

## computation

al problem that is hard but what I like to call a computational puzzle that is hard the distinction between a puzzle and a problem is that a puzzle in a puzzle someone who made it someone The person who invents the puzzle, the person who designs the system, who chooses the keys, knows the answer, knows how to solve the problem, but the attacker, the person who reads the puzzle in the newspaper, does not know how to solve it, so those two barriers go from the worst case to the average case.
The complexity and average complexity of the case would remain after solving for P versus NP. Thanks Russell um Sandy Rani will tell us how quantum computing influences these issues. Sandy earned her PhD at Berkeley in 1991. I'm proud to say that she was my student and she's a professor at UC irine um, so there's been a lot of interest in the press recently about the prospects of quantum computing and the idea behind it. Quantum computing is that the physical world at the atomic scale is governed by the laws of quantum mechanics. which are fundamentally different from the physical laws that govern the macroscopic world, so the hope is that we can somehow encode information at the atomic level, perhaps in the spin of electrons or in the energy level of atoms, and manipulate it in some way to take advantage of the Dynamics of quantum mechanics to solve computational problems now.
We don't yet know if we can build large-scale quantum computers, but theprinciples of quantum mechanics that would be used in a quantum computer have been confirmed experimentally on a small scale and based on those principles, we have developed a theoretical model of what a quantum computer would be like and one of the most famous results in quantum computing is due to Peter Shaw and showed that if we could build a quantum computer. then we could factor numbers, so Mike prepared me perfectly for my Spiel because he explained to them how we think factoring is really difficult in classical computers and it's an extremely important problem for cryptography, so if we can build quantum computers, then we could potentially To crack modern cryptographic systems in commercial use today, the question now arises: could quantum computers be used to solve these so-called NP-complete problems?
Can we move on to the next step? um and there we are a little more pessimistic and one of the mysterious and beautiful things about quantum mechanics is that it says that matter actually exists simultaneously in different states, so the natural thing to do with a quantum computer would be to use these multiple states to prevent parallel exploration of different possibilities, so we would take the search problem that Mike talked about, say cleck, and each different state would simultaneously explore a different possible subset of nodes to see if it is a click. Well, the problem is at the end of the measurement, so the problem is that if you've stored your information in the spin and the electron, you can't just look inside and see what it's doing, you have to make a measurement and the result.
The measurement not only changes the system but also gives us very limited access so it may be the case that one of these possible states has discovered a click of a certain size but if we measure the system it is the event that we really discover doing click has a very low probability, so there is actually a theoretical result that is a bit complicated to explain here, but it says that exploiting quantum parallelism in such a naive way is not going to work, so that basically leaves us in a state that is very similar to our understanding of NP completeness in classical computers, the idea is that we basically have to understand a lot more about the structure of these problems to know if they can be solved on a quantum or classical computer, since it turns out that factoring has more structure. and that's why Peter Shaw was able to exploit that structure to use quantum computers, but we don't know if that structure exists in these other kinds of search problems that are NP complete, so okay, now let's move on to the math. logic, uh, Ron Fagan got his PhD at Berkeley in 1973 in the logic group and is an IBM Fellow at the IBM Aladen Research Laboratory, thanks, idiot, so I think all scientists should spend at least a modest amount of time each year to think about the most difficult problems in your field, so I in particular spend several days at least each year thinking about the P versus NP problem.
I don't know if I'm a nutcase. I mean, some people say you spent 40 years thinking about a problem. You're crazy? But anyway, I think about it and the approach I use as Dick mentioned is logical. Probably the result I'm best known for is something called the Fan Theorum, where I showed that the problem is an NP if and only if. expressed in a certain language l uh, then, using that approach, I have proven at least twice that P is equal to NP and at least twice proven that P is not equal to NP um and proof that the latter is the most long.
I had a proof that P does not equal NP that lasted three days. I showed it to him while he still believed it. I showed it to a famous theorist who couldn't find the problem. Then after finding the bug just for fun, I decided to visit some famous theorists to see. if they were able to find the error and uh two of them one of which is on today's panel I'm not going to say who couldn't find the error uh and it turned out that the error was that he had misused Fagan's theorem and so I think it's probably That's why they couldn't find the error because they gave me a pass.
I mean, if anyone knows how to apply Fagan serum, it's Fagan, so that part has to be right, oh thanks Ron, it stands to reason Mike should do it. I have the last word before I just want to pay tribute to a former Berkeley professor, Manuel Blum, a great leader in our field who moved to Carnegie Melon University and who was the thesis advisor for three members of our panel, one of which is Mike, thanks, idiot, um, so I just wanted to follow up on Ryan's comment a little bit, um, about um, you know, is it possible that the P versus NP question is beyond mathematics?
Could it be that the basic concepts are axioms of mathematics that we? I've accepted that you know that for a century or more there simply aren't enough to prove P versus NP one way or another. That situation is known to occur for some other problems in mathematics, for example, some of you may know that there are different sizes. of infinity, the infinity associated with integers and the infinity associated with real numbers are not the same. Infinity, real numbers actually are. I mean, these are the numbers with all the decimals and, as opposed to just the whole numbers, the real numbers.
It is known that there is a larger infinity, so a question that Rose posed very early in this theory of infinities is whether there is an infinity between the size of integers and the size of real numbers, and it was eventually shown that that problem had no solution using the basic tools of mathematics it just doesn't follow from the basic basic axioms, so maybe that's also true for P versus NP and some of these results that Ryan mentioned there are some barriers that suggest that certain methods don't they are going to work. I just want to state for the record, I don't think that's true.
I think that, um P, the P versus input problem is a problem of a different character than these problems about, say, Infinities or these other types of independent problems because those problems deal with things that are very far from our ordinary intuition n p versus NP is something that is very basic and I think the axioms give us enough strength if we are just smart enough to answer questions like P versus NP, but you already know these theorems about barriers. I think you really know this may be unfair, but basically the amount is showing well the methods that we know so far are not going to work well, that's true, they don't work there, you're going to take something.
We're going to take a new, completely new, radically different idea, but just because we've been working on this problem for 50 years or whatever, you know, we haven't solved it, doesn't mean it's unsolvable, we just haven't solved it. I haven't been smart enough, okay, so at least it's an optimistic note, I think, so I guess now that we're supposed to answer questions or we have questions to have a panel, I have a certain amount of audience questions here. , so we'll go over some of the questions that have come up from the audience and I'll read the question out loud and if you think you're the best person to answer it, raise your hand.
Okay, if the P versus NP problem was solved tomorrow, how would the world be different? Scot MIT has spoken on many topics. Oh, sorry, Scott Arenson, a professor at MIT, has talked about that same problem and the way he describes it if P. equals NP turns out to be true, then we are in a very different world than where we are today, so For example, cryptography wouldn't work, a lot of things wouldn't work, you would lose your privacy because the codes would be easily crackable, so uh, it would be a very different world we would be living in if P were equal to p and we believe that P is not equal to NP We think that's our world, but we don't know how the world would be different.
If we knew that P was unequal to NP, we would be much smarter, just like the things we would have to know about part-time calculus about physical calculus would be so So deep and vast compared to what we know about what computers can do, there would be a lot of other things. consequences, it's like it would be impossible to prove P from MP and not prove a bunch of other amazing things about feasible calculus like that, that's how deep the question is. Great answer, thanks, okay, here's another one, suppose P equals NP. but the degree of polom for NP-complete problems is prohibitively high.
Maybe I get 42, what's your reaction? Well, I'm not sure that 42 is that big, but, you see, I think I think, people, I think maybe this question is a very common question. It's not a very good question, but maybe it's also a bit of a misguided question because polynomial versus exponential was kind of polynomial versus non-p polynomial was kind of shorthand for converting a quantitative problem exactly, how hard are these search problems? in a qualitative problem? and um, if it turned out that the actual execution time, if you let me tell you if you had a lower bound on the time to solve the End of Thousand surge problems, if you knew that the surge problems required an enormous number of polynomials, so you would say in some sense the problem was solved, okay, um, if on the other hand you knew an upper bound, an algorithm that took time to become a very slowly growing function, in some sense the problem was solved or done a lot progress even if it were not. technically it doesn't answer the problem of P versus NP, the sad case is that we are not, no, no, we are not even close, we do not have a super linear time limit, we are not close to N at 42 that we do not have n until 40 we don't have a lower limit N squ, okay, so we're not close at all, give me an ending for the lower limit 42.
I'll be ecstatic, give me an ending for the record. At the upper limit, I'll be ecstatic, so exact polynomial versus non-p polynomial is just the easiest way to express the problem, it's not really the be-all and end-all, anyone want to disagree with me or, well, you think that P is equal to NP. why equals equals I don't want to go on video saying that an allowed answer is no, yes, so I think maybe we could. I guess I don't think there's any reason to believe that P equals NP, but you might be skeptical that P I know that maybe our belief that P doesn't equal NP is A baseless, you know, so, you, I , I can see being agnostic, but I can't see being a firm believer that P equals NP at this point.
I just want to comment that there is a type. His name is Michai at IBM, he's a brilliant theorist, and he believes that it's very possible that P equals NP, but that the algorithms to solve, for example, the cek problem, are incredibly complicated, that is, so full of loops and this and that than any human being. we can understand it no, we are unable to analyze it, so it could be true, it's just that we are not able with our limited minds to even understand it or prove it. What about other galaxies, other universes, maybe I really like others? universes, but that's a whole other story, okay, okay, here's another one.
Why can some problems, such as pattern recognition and perception, be solved faster with people than with machines? Okay, I guess the short answer is, look, how much time has passed? has had to design good programs for these things and how much time have people had to design good programs for these things that we're talking about, you know, 400 million years versus 40 years, so evolution has a good head start on us, Yes, Mike, let me. just add to that, you know, I think, speaking a little bit, you know also interpolate what Ryan said, you know that not only do we not understand how to prove things like P, you know that P is different from NP, but I think it's entirely possible that I don't really understand the kind of algorithms, that there are amazing things that the brain does that we have no idea about and it's conceivable that there are some amazing procedures that we have.
I haven't discovered them yet because they are very complicated or very deep in some ways and you may know that you know that understanding the limits of computing can also help you understand something about its capabilities. Very well thank you. Here's one that Edward Snowden could. possibly he answers huh, is it possible that the NSA has worked out that P equals NP but isn't telling anyone that it does and how would we know? I don't know, of course it's possible if they knew they definitely wouldn't tell anyone, but actually Edward Snowden gives us a big clue because in his Revelations he said that the NSA was setting trapdoors to weaken encryption standards and, um , and also, you know, harassing tech companies into revealing passwords if they already knew how to crack P versus NP.
They wouldn't have needed to do those things unless they wanted us to believe what is the most notable false proof that P is equal to NP or P is not equal to NP that you have ever encountered. I don't know if I call it notable, but there was a very, very publicized U uh attempted proof that P is not equal to NP that a few years ago by dear in the HP labs and one of the interesting things is a whole lot of themathematical community, including Fields medalists, etc. I jumped on it and analyzed it. I mean, this is the worst possible group of referees if you're your nightmare group of referees if you're a writer because these are brilliant people who penetrate to the heart and discover and, in fact, one.
Of the people there was Ryan at the end of the right who found a basically brilliant argument that his approach couldn't work, although he still doesn't accept it himself, but it was notable in the sense that it really lit up the community for people because It's a very exciting approach that didn't work, but it was a very exciting approach that really sparked the community to take a hard look at it. I think you know it would actually be difficult for someone who is unwell. known in the field and has a proof for the community to accept and I was discussing this with a friend who is editor-in-chief of a major journal and receives daily proof that P is equal to NP and proof that P is not equal to NP and there's no way you can read them all and sort them and they're not refereed and I just said, you know if it happened that someone came in who wasn't very well and had a lot of credibility. to get a proof, it would be a very difficult process for them to get that proof read to be accepted because it would probably also be very long and complicated in the first place, so there's sort of a social process in the math community to get a test.
I agreed um and it would be hard to go through that if you weren't, if you didn't already have some credibility, so, to Mik, I mean, I can say I've already received several.dozen um claims uh, they're in two I'm not sure that they're notable, that's what they are, they're all the same um, there's evidence that P equals NP and those are inevitably some long, messy algorithm. with a statement like well, I ran it on a The Click problem with 300 nodes on my uh in Turbo Pascal and it only took 14 seconds, what are you going to do with that?
So I always respond to those people, see if you can really try it. p equal p you can take your algorithm and factor big numbers and there are some famous ones online Factor one of those numbers and then come talk to me, okay, so it's an easy test, because I mean read those algorithms, forget it, I mean . Those are always very complicated, then there was the evidence that P was different from NP and, with the exception of the Dakar argument, which at least had the possibility of providing plausibility, the others always look the same, if you scan them, they always look They look the same. they have somewhere a statement that, well, you know, long preamble, blah, blah, blah, blah, blah, but somewhere they say: well, clearly, an algorithm to solve clickability or satisfiability or any of the others. difficult problems, say click, an algorithm to solve click has to operate in the following way clearly and then they have a long analysis because that will take them exponentially time, but that's the point, they know it clearly because algorithms can operate in some roundabout way and there may be things that are not so could, may, you don't understand, that could be the algorithm, so you know you just have to find it clearly and then you can knock it down anyway, that's been my experience, you know several cases, like that what's up.
There have been a couple of P tests attempts to prove PS and P that led to barriers to barriers tests, so basically some people had come up with algorithms for the final travel problem and they didn't work, people found counter examples. and then they came up with more complicated algorithms and this shows that this forced researchers like my yanakakis at Babs to find a test that listens, no matter what you know, this approach will never test the barriers, okay, I think it's a test that It forces researchers to prove that an interesting theorem like that Yanakakis is the lower bound is a remarkable proof.
You should also know that in the late '70s my friend I was then at Harvard Harry Lewis and I wrote a Scientific American article on this question P versus MP and we posed some whole MP problems and this was maybe and we got in response probably many dozens of what would be very early attempts at equals and being okay, you know people you know that were some kids, some old ladies that wrote to us, uh, who. I wrote, you know, I think I can solve the graph colony problem and here's an algorithm, okay, so we decided to read them all and find a counterexample and basically let you know that we ran a contest, okay, so now You know, we decide more.
A notable attempt would be the one that required the largest counterexample and unfortunately this didn't work very well because the winner was a guy who said uh, if the graph has less than 15 notes, do it exhaustively, you know, and otherwise, and then Of course, I stumbled, you know? I just want to comment that there is a page on the website. I think it's called the P versus NP page, but I'm not sure where you have a very long list of attempts to solve P versus NP, so it has the name too. from the person and some comments on what the approach is, so if you google the P versus NP page you will find this long list of attempted solutions, so there is historically notable proof that P does not equal NP um from I Think about the early 70s in the Soviet Union, so maybe Ryan knows better, anyway, a person who posed the P versus NP problem, an equivalent problem in Russia, unfortunately wrote a fallacious proof that P was essentially different from P. was different from NP, the language was slightly different and because of this fallacious proof that was accepted because this person was politically influential, it almost ended complexity theory in the Soviet Union, in fact, practically ended complexity theory in the Soviet Union, um, the people who managed to um like Leon 11, who managed to do complexity theory in the Soviet Union, did it by immigrating, um, so that was probably the test historically more important than that P nope, okay, it was a breakup, yeah, yeah.
I would like to thank the audience. for your attention and for the wonderful questions you have raised and also thank the panelists for their interesting comments.