What Computers Can't Do - with Kevin Buzzard

Kevin Buzzard explains one of the biggest unsolved problems in theoretical computer science - the P vs NP problem.

Today’s computers are lightning-fast. But sometimes we want to make sure that they can’t solve a particular task quickly (perhaps for security purposes). This issue lies at the heart of the P vs NP problem, one of the most famous conundrums in computer science, which Kevin Buzzard will explore in this Discourse. Can every problem whose solution is quickly verifiable by a computer, also be quickly solved by a computer?

Kevin Buzzard is a British mathematician and currently a Professor of Pure Mathematics at Imperial College London. He specialises in algebraic number theory.

[Thanatos]

You can tell it's a proper math talk when the slides were made in LaTeX.

[Sychonut]

Dude walked 10K laps around that damn table.

[KelnelK]

That's quite a choice in trousers to wear for a lecture at the Royal Institution

[yuricahere]

16:48
problems reviewed in class: bisect an angle
problems on the test: trisect an angle

[FarnhamTheDrunk]

damn i had to check my youtube speed cause i was SURE it was running at 1.5 speed ^^

[pyroslavx]

As far as i can remember that "killer robot" is ment to be "just" a transporter thingie, replacing a mule/horse/camel (or human) carying heavy objects on terrain where regular 4WD vehicles can't go, no weapons added (for now)...
We have way more effective (and likely cheaper/less complex=less worry if they get shot down) flying killer robots-drones.

[CyanBlackflower]

I love this channel. I try to watch and fully understand/comprehend at least 3 of the lectures posted here, per week, choosing a variety of topics to learn a little more about diverse subjects. Taking them in and taking time to digest and contemplate them, at my own rate, is making a big difference in the way I see and deal with the world at large. Expanding one's "horizons" in ANY way is never a bad idea IMO.

[filthyfilter]

Lord Voldemort in pijamas pants and fine costume explaining awesome things :D

[jamesh]

Finally someone using beamer for a maths-based presentation. LaTeX for life!

[handle]

The problem with saying that computers can't 'think' is that you are comparing something that is known very well (what computers do), with something about which we know almost nothing (how humans think). Neuroscientists have literally just scratched the surface on the subject of human thinking and we may find, as we dig deeper into human thinking, that at the bottom there lies a series of basic operations akin to computer instructions, that is every bit as predictable. A comparison such as that, between something known and something unknown is essentially meaningless. Anyone claiming to have an opinion on the subject really has nothing more than a guess - and not even an educated one.

The reason why we feel intuitively that human thinking must be very different to what computers do is down to the old saying 'familiarity breeds contempt'. Our familiarity with computers leads us to downplay what they do, while our unfamiliarity with human thinking (as in how it works) leads us to treat it with a degree of awe and wonder that may not be due.

[nathansnyder]

As a philosophy graduate who had never encountered the computer science P vs NP problem before watching this, I first read the description to be the formal logic "P or Not P, " and the concept of computers struggling with that made me chuckle.

[mattjones]

The idea that proving P=NP true would lead to all these shocking consequences (e.g. encryption breaking) assumes that any proof of P=NP would be 'constructive' i.e. that the proof itself would outline *how* (construct) we could quickly prove (move to P) something that's quickly verifiable (NP). This would be some general schema or framework applicable to any NP problem, like a computer program.

Proofs, however, needn't be constructive: they needn't actually design some process to achieve the desired outcome but, rather, show its truth based on general principles. Mathematicians don't all agree that a P=NP proof would necessarily be constructive.

So, even if P=NP is proven to be true, if the proof is non-constructive then we needn't immediately worry about chaos ensuing. Designing methods for 'cracking' individual NP problems might take an unreasonably long time (indeed, we've failed to do so for many basic ones so far e.g. factoring), so the impact would be limited.

[recklessroges]

first 35:00 minutes some computer history working up to explain The Halting Problem. Then the rest is, "We have yet to prove is P=NP or (P not = NP)".

[rangersmith]

It remains very difficult (maybe impossible) to prove that a thing does not exist. I demonstrated this in teaching logic by telling students that I might have hidden a $100 note somewhere in the room. They were charged with proving that I hadn't. Of course, no class could ever do it. Now I know why; it's a problem in NP. If I give them the location, they can easily check to see if the money is there. If they can't find it, I can always note a place where they haven't looked.

[sugarfrosted]

I bit my tongue when he said the halting problem being intractable is "theoretical computer science" and was differentiating this from mathematics. Computability is part of mathematics.

[trudyandgeorge]

It's funny, the description of how the computer doesn't "think" was to point out that Kasparov wouldn't exhaustively go through each potential next move in his mind, he would employ some intuition and other "thinking stuff", whereas the computer basically exhaustively goes through each move until it finds the next best one to play.

This is in fact not what the computer does. The whole point of computers playing chess is because of this fact. Chess has too large a search space to simply blast out a tree and collapse back on to the highest scoring leaf.

[bit_pineapple]

The first description of AI with the conclusion that computers can't think is awfully outdated. For a less outdated comparison we shouldn't be comparing Garry Kasparov vs Deep Blue, we should be comparing Lee Sedol vs Alpha Go. The main difference here being, alpha go uses an artificial neural network -- the search space is too large to simply use a brute force approach. So Alpha Go makes decisions in a manner that resembles intuition, it picks the moves it "thinks" will be best based on games it has previously played/seen and it narrows the search space by only evaluating moves it "thinks" are most relevant.
Whether or not it's _really_ thinking to me seems to just be a matter of semantics. I've yet to see a list of criteria for "thinking" that is demonstrably applicable to biological neural networks (brains) but not applicable to artificial ones.

[kenh]

Thanks to the RI and Prof. Kevin Buzzard for a fast show intro into what's computable and what may not be. Brilliant!

[antonnym]

As an extra note: If you're looking for prime factors, then as you are testing whether a divisor is composite or not, the shortcut is that you have to test only up to the square root of the number you are factoring. e.g. SQR (100) = 10, which means to find all prime factors for 100, all you have to do is test the prime numbers between 2 and 10 (2, 3, 5, 7) And that's GAG (Good As Gold)

[jerklecirque]

He seems to take a very limited view of what an algorithm is, suggests that we don't operate in quite that way, then concludes that computers can't think. Maybe he only means "computers as we have traditionally known them so far can't think", but I suspect he's going for a much stronger statement without giving an argument.