Q&A - What Computers Can't Do - with Kevin Buzzard

can I use my dorm pocket when asked the first question if I've understood you correctly it's actually all the works been done with computing won't actually solve these problems so quantum computing might make the problem less relevant because there's there's you see once you once we have a quantum computer then suddenly there's a new class of problems right there can be QP it can saffron's we can solve using quantum quantum computer and b QP we don't know we can't prove anything right we're really not very good at brewing that a certain class of problems is different to a certain other class that's exactly the thing we can't so BGP will sit somewhere in that picture right so all the all the pollen all the things we can solve quickly using a normal computer for you definite self really using a quantum computer but there are things which you can solve Queen factoring is a great example we can solve factoring quickly using a quantum computer and so if quantum computers actually do become real that we might start reevaluating the importance of the PC that's what happened with bisecting angles that was important at one point right it's quantum features become real and in 30 years time none of us had could use anymore we are quantum computers then the question has changed you see so the answer is quantum computers won't resolve the problem but they might make the problem less important and but but here let me let me just say one thing about quantum computers that you do see companies to the claiming to build quantum computers but there's a very famous there's a very famous 617 digit number that was that was invented by some guys and not invented I mean dates they took three to three hundred digit prime numbers and ties them together made a six hundred digit number and they put it on the internet and they destroyed the computer that they'd used to compute the store integer numbers and they said dating the factor that and that's thing and that six hundred is number and they offered a big reward but it last and no one is if somebody if somebody had a real quantum computer they could factor that six hundred each number okay but until that six hundred digit numbers factored I do not believe that quantum computers whatever you read in the popular press okay play pop in other words right right questions common hello oh who chooses I choose okay whether but when I see a hand going up there's a helper yes I yes yeah okay wait for microphone to come hello I'm Kevin I don't firstly thanks for the talk there's no really good and I can see that proving P is not equal to NP is one class because all you need to do take one empty problem and prove that true is going P yeah yeah and then you've solved that problem clearly not equal but proving the other way round is going to be trickier because you have to take every problem that's in NP and make it P wrong okay can I have the visualizer on there are certain problem I can see the phone's off so that was the case in 1971 but a few years later there was his breakthrough some people realize some people isolated some of the hardest problems in NP okay the hardest followed in NP are things called NP hard problems or emptiness and while they showed because if you could solve just one np-hard problem quickly then you could solve all NP problems quickly so if there is actually the NP problems are kind of in a list and they've worked out what's at the end at the end is a whole bunch of problems which are the hardest NP problems so all you have to do is solve one of those NP problems and by I've got so like pokemon is a great example I was going to show you some I mean I was going to show you an app on my phone that happens to be np-hard but Pokemon is a button sig Mario Brothers as well if you could write a computer program that just looked at Super Mario Brothers level and work out quickly but or not you can play it then you prove P equals NP okay so you can play Super Mario when your mum asked you what you're doing you say you're working one of most important forms of a person so yeah you're at yeah well spotted you're absolutely right so read about np-hard problems those are the hardest just solve one of them and you solve them all so it's very very clear what the job is you've got to solve will either prove you can't solve one problem quickly or prove a certain yeah a certain list them there's thousands of them now you just go solve one of these thousands of problems and you've done it so that's what you should work on if you think it's true please can write for microphone John do you do you think that our chaotic systems are hard problems that would just cannot calculate can you ask the question again so if you have a system that's cause you have to be chaotic uh-huh do you chaotic did you say chaos yeah yeah okay so do you think this is an np-hard problem at all kind of actually calculate okay chaos somehow on the boundary between physics and mathematics I think that isn't it ah I think if I tried to get my computer to emulate some chaotic system then isn't there isn't there problems with the register things getting so close to each other I don't well I wonder whether well I thought yeah I'm not the person I don't know anything about chaos theory I think that there are problems in chaos theory that are np-complete so you do see the phenomenon you do see the phenomenon there but I can't I read on the internet that would be able to will be also predict the weather better but I don't know I'm sorry I don't know I don't anything about this stuff at all and I sure didn't quite know throwing looked on having macros that's this game here sorry let's do that later this game here is np-hard pushing all these little squares on it I've been playing this game a lot recently and this is a great if I work out how to do these levels really really quickly that I prove P equals NP and you know that what what is really really quickly mean I mean I need to well quicker than I'm doing now quickly means quickly means can I can I feed that level into a computer and can be computer tell me how to solve that level see I can I can figure out of this I can press the hit thing and the computer will tell me additive but the computer knows if the computers been told the solution but you see humans design these cells and computers are quite bad at solving them it's the question over there right hey um obviously there's things that we sort of know true empirically but we can't prove thinking about this the other way round how does proving that something is possible actually make those applications that you put on the board that are quite specific more probable in yeah to be solved so so I suppose that's it yeah I so I've told us died in some sense because you've seen you've seen in this talk very abstract ways of proving things right and there are certainly very RI there are very abstract ways of proving things in mathematics where you prove that something can be done but don't actually exhibit any way of doing it so in some sense I've told you lies because because in theory it's possible the mathematicians will be able to prove abstractly that P equals NP in such a weird way that it will give us no way of will give us actually no answering it so yeah so flaw in the argument however it's very difficult to be in this using our code if P equals NP was proved now is probably not going to be fruit pie that is for it that's what it P if P equals NP was proved now it's probably because someone's going to take one of these np-hard problems and and solve that and then everything else once that happens that will follow but you're absolutely right there's a theoretical possibility and how frustrating would that be that we end up proving abstractly to P like there's one one other possibility is we prove that it's impossible to prove what a pig was MP or not that could also happen so there are these sort of boundaries there are boundary issues it's impossible to prove with a pig with AB you know in mathematics and so then we have to maybe starting about what mathematics is and changing our definitions I mean yeah weird of things can happen but yeah your absolute you're on it but I don't think it's identity is likely but I think it's likely the P is an NP okay one last question okay he's here hello go back for microphones job place with microphone coming I can't imagine what you're about to say reminded me that you told remind me a lot of Bitcoin and oh yeah yeah we'll see around Bitcoin it struck me that yeah yeah this is decreasing Bitcoin that slew that is a Bitcoin an NP problem to K if you have the public and the private yeah oh yeah absolute if you don't have it it's impossible good all but it relies on it yeah yeah if P equals NP then bitcoins broken but I mostly would own all bitcoins I yet so like 10 years time I'll give this talk again like that might be yeah yeah absolutely bitcoin is an example of an NP problem i think bitcoin is yeah bitcoin is in big condors NP problem so yeah stealing other people's bitcoins is is a not known to be easy germany bitcoins yeah how many do you that's a real question so i got i got less than one but you need the bitcoins to buy the drugs on the end that you know that while coupons that draw things to conclusion it's just relate to think it's a super difficult thank you you

Channel: The Royal Institution

Views: 21,675

Rating: 4.8927836 out of 5

Keywords: Ri, Royal Institution, science, computing, mathematics, lecture, kevin buzzard, computers, p vs np, p problem, np problem

Id: A6J9p4iOr3A

Length: 10min 41sec (641 seconds)

Published: Wed Aug 02 2017