Donald Knuth: P=NP | AI Podcast Clips
Вставка
- Опубліковано 3 січ 2020
- Full episode with Donald Knuth (Dec 2019): • Donald Knuth: Algorith...
Clips channel (Lex Clips): / lexclips
Main channel (Lex Fridman): / lexfridman
(more links below)
Podcast full episodes playlist:
• Lex Fridman Podcast
Podcasts clips playlist:
• Lex Fridman Podcast Clips
Podcast website:
lexfridman.com/ai
Podcast on Apple Podcasts (iTunes):
apple.co/2lwqZIr
Podcast on Spotify:
spoti.fi/2nEwCF8
Podcast RSS:
lexfridman.com/category/ai/feed/
Donald Knuth is one of the greatest and most impactful computer scientists and mathematicians ever. He is the recipient in 1974 of the Turing Award, considered the Nobel Prize of computing. He is the author of the multi-volume work, the magnum opus, The Art of Computer Programming. He made several key contributions to the rigorous analysis of the computational complexity of algorithms. He popularized asymptotic notation, that we all affectionately know as the big-O notation. He also created the TeX typesetting which most computer scientists, physicists, mathematicians, and scientists and engineers use to write technical papers and make them look beautiful.
Subscribe to this UA-cam channel or connect on:
- Twitter: / lexfridman
- LinkedIn: / lexfridman
- Facebook: / lexfridman
- Instagram: / lexfridman
- Medium: / lexfridman
- Support on Patreon: / lexfridman - Наука та технологія
We study this guy as "aspiring computer scientists" at Uni and he's still among us, thinking about this is huge, he is a ComputerScience hero of our times for sure
He is referring to the Robertson & Seymour graph minor theorem. Every class of graphs that is closed under minors has a finite obstruction set of "forbidden minors". This follows from the fact that the graph minor relation on the class of all graphs is a quasi-well ordering.
You can look it up on wikipedia.
The point is that this theorem constitutes a non-constructive proof for the existence of PTIME algorithms for every class of minor closed graphs. I.e. we know that a PTIME algorithm EXIST for each these classes, but we do not know what exactly the PTIME algorithm IS for each individual class, because for this you would first need to know the finite obstruction set of forbidden minors.
So this theorem contradicts the intuition that the only way to find out whether a problem is in P is to write down an explicit algorithm for solving it. You can know that a problm is in P without knowing what the PTIME algorithm for solving it is. And this might suggest that you really can't conclude that P!=NP just from the fact that no one has found a PTIME algorrithm for a NP-hard problem yet.
I first learnt about the series of 20 papers on graph minors while searching solutions to the kdpath problem on grid graphs, and I remained absolutely stunned
Thanks for the clear writeup. This also hints that there may exist possibly optimal polynomial algorithms with mindboggling constants, like googleplex, or Tree 3, etc., by existence of graph classes closed under minors with that many abstract representatives. Indeed I could believe that many games have such a polynomial but unpractical solutions...
There are numerous economy of such examples of non constructive proofs in the literature
This man is 83 as of today. His book TAOCP was and is the base “Bible” of Computer Science since I’ve been alive. I am humbled to hear this man talk.
More like the old testament, in which he is Moses and Alan Turing is Abraham! 🙂
“... they all discovered machine learning and blew each other up.”
😂😳🤦🏻♂️
I think that is the best and most realistic explanation so far: think about nuclear weapons, we have had those for little more than half a century and we barely escaped blowing ourselves up in the cold war a couple of time, imagine the next level class of weapons, like the "grey goo" or self replicating nano machines...At some point technology will came up with weapons that are way more destructive the nuclear weapons while being way cheaper and easier to mass produce.
@@freedom_aint_free Yup that is one version of what's called The Great Filter.
Hah the end was very american lol
@Roberto Gatti A huge stack of linear algebra mixed and lots of guys tagging datasets
I find it funny that people on UA-cam mock what they know so little about, all pretending to be experts. You aren't doing the world any favors. In fact, you might be a significant cause of its problems. Stick to mocking what you actually know and leave mocking of actual things experts do to the experts. Or, not, and watch your world continue to deteriorate into Idiocracy.
This guy was one of my heroes growing up. Thanks for all your work on the show, Lex.
Lex!
This shot format is "damn chill".
Tiny room win.
Lex, I first got introduced to you from JRE. No shock there. But I must say that your podcast is absolutely amazing. You ask the questions I want Joe to ask his guests when there are scientists on and I love t. I don’t really have any huge criticisms of what you do. I am just very thankful for your format. The adds in the beginning, like Joe’s format. A great idea. I’m fascinated by the people that you interview. Your questions are all the questions I would like to ask. They are philosophical in nature and also you are not ill-informed to when it comes to asking complicated technology or physics questions.
Wow, the legend Knuth himself. His books really did put my knowledge to the test
did you work through all the volumes of TAOCP
@@ashutoshpadhi2782 1,2,3,4A
@@benzel5659 i want to discuss with you regarding this, can you share your WhatsApp
Wawoo i have been listening to this full interview over and over to get a full grasp of everything he is saying, thanks Lex, Great stuff really
Absence of evidence is not evidence of absence. Humble geniuses like Knuth never forget this.
re: Donald Knuth - Another observation, It's obvious he's trying to translate years of thought at the highest level on the subject while trying to remain unassailable to others versed on the subject, all the while he's working through ideas.
duh
Just learned about Kuratowski's Theorem and now I'm here. Thanks algorithm.
This channel is love..!! 😍
I wonder that for a long time thank you for that
4:16 lex lookin like a mob boss
If he's right, then we don't get a solution to NP problems, but at the same time a whole bunch of categories they've painstakingly constructed over the years on the assumption that P isn't NP collapse into one. The worst of both worlds...
If the algorithm is never written down does it really exist?
*A wild Platonist appeared*
If your dream is never described to somebody did the dream exist? Does it exist after it’s over? Do memories exist?
In the case of dreams, you have first-hand experience of them. The same cannot be said of all possible algorithms.
But just because you cannot completly grasp something does not mean it doesn't exist.
For example: no one can ever fully grasp pi. We can compute digits of pi till the world ends. Is the last digit we compute the last digit of pi?
There exists an algorithm that outputs the correct anwer to this question.
It's got to be one of these two:
1. print "yes"
or
2. print "no"
:-)
Marco Acuña sure you can grasp pi, you just can’t grasp the decimal representation of pi.
Best music. His voice is melodious. That’s all I can say.
There exist rather simple algorithms that completely solve Hex, in the same vein as for similar complete-information games like chess. Just minmax through the game tree. It obviously gets prohibitively time-consuming as the board size grows, but the algorithm itself is rather simple. Am I missing something here?
I think the algorithm you described is basically brute force and is not polynomial time. Chess may not even be an NP-complete problem because even if you were given the perfect solution you could not verify it quickly without the same brute force algorithm. NP problems must also be verifiable in polynomial time. I don't really understand his example that well either but I think he's basically saying just because we haven't discovered it yet doesn't mean we should just assume its not equal.
P.I.M.P.
Can anybody tell-me/point-to more about what was said at 8:00?
Eu acredito que vamos achar ! E concerteza vai ser um brasileiro a ganhar o nobel
10:07 - What prizes are those??
Loosely related but intriguing enough - quantum computers and NP-complete problems. In short - the BQP class is a "slight" superset of P, hence NP-complete problems are out of reach of quantum computers. Sad again.
Really? I thought we finally had a shot of NP complete problems with Quantum Computers. BQP is quantum possible solution space?
@@vamvra5498 Not really to the best of my knowledge. Prime factoring is NOT NPC, so ... plus, remember - all quantum computing is giving you a result with certain PROBABILITY - not like our "classic" algorithms.
Proposal: Assume you can solve the halting problem using a non deterministic touring machine. I think this is a good assumption that can be accepted. Because such a machine can then be used to build another machine that leads to the contradiction that such a machine cannot exist, this looks to be a valid proof of contradiction to me. That is. Non deterministic touring machines cannot manifest themselves in reality (i.e. banished to the realm of thought experiments) and therefor P != NP
That assumption is provably false because non-deterministic Turing machines are computationally equivalent with deterministic Turing machines, e.g. by introducing multiple tapes (this is fine because N^3 is in bijection with N). It is easy to find a proof of this by search engine (not sure if I can post links).
Yea true. But if a non deterministic Turing machine can't solve this halting problem easily, how does your boss seem to do it so confidently? Boggles the mind.
@@imensonspionrona2117 But the halting problem is undecidable, therefore the assumption is false. Citation: Alan Turing
Here's a prime example of a strong interview subject for a written article, not an audio recording
Not only is the subject matter visual and of document form, best understood in documents, but the interviewee is obstructing a clear view of the material.
I wonder if someone can link to a reference document, please.
There is a huge amount of written material on the subject online.
I think you're missing the point. This has nothing to do with P=NP. Donald Knuth is the subject. I've always liked the way he speaks. I don't care anything about P=NP, but Donald Knuth, the person, is fascinating.
@@mtae5 thanks, that was fun to read
The machine learning comment 😂😂😂😂😂😂
I lean towards thinking that P != NP. I don't see how, in general, having a poly-time algorithm for verifying a solution to a problem means there is a poly-time algorithm for finding the solution.
It's a bit like asking "If you can quickly verify that your keys are in a certain place, can you quickly find them in your house?" Obviously this is not true in general. In the worst case you still have to look all over your house.
yes you can. the time it takes to find the keys is O(n^3) for n being your house length.
Polynomial time doesn’t necessarily mean fast.
@@tylerfusco7495 I agree, searching your house takes poly-time in some sense. But the point I was making is that the size of the search space often has nothing to do with how quickly you can verify the solution. For example, the size of your house is not restricted by the time it takes to recognize your keys.
My intuition is that if there are problems encoded in n bits that have a O(n^k) search space take Ω(n^k) time to find a solution in the worst case, then there should also be problems with a O(2^n) search space which take Ω(2^n) time to find a solution, even if verifying the solution takes O(n^k) time.
@@philipcervenjak2493 as I said above, the "guessing" stage of NDTM does not say ANYTHING about a potentially existing algorithm. The more I am thinking about the NDTM definition (and NP completeness generally), the more I think it is flawed - sorry to say that. NDTM is not helping in practical solubility of a problem. Think about 2SAT and 3SAT - the former is in P, the latter NP, even NP-complete. What is the difference? The 3SAT has ONE MORE literal in the clause - and we are moving from polynomial resolution to exponential intractability. Sad. We do not know the 3-resolution algorithm, we do know the "2-resolution". It is like 2 - tractable, 3 - not at all - Fermat theorem ends at n=3 as well (not related but I can't help myself :-) - but perhaps a new math/theory hitherto not known is needed here for P=NP as well. Again - NDTM is a flawed concept IMHO.)
@@Ezop1959 I agree that we need a new theory to tackle the P vs NP problem. The only promising theory that I'm aware of is geometric complexity theory (GCT), which is too difficult to grasp for most people including myself. But even on Wikipedia (en.wikipedia.org/wiki/Geometric_complexity_theory) it says that one of the main proponents of GCT thinks it will take at least 100 years to settle P vs NP.
@@philipcervenjak2493 I think you misunderstood what Knuth's argument was. I don't think it had anything to do with having a PTIME algorithm for verification leads to a PTIME algorithm for a solution. I believe he is saying that since there can provably be a PTIME algorithm for a solution without knowing what the algorithm is, then it isn't a far reach that there could be a PTIME algorithm to a NP complete problem even though we haven't found one. His argument is more about intuition not about logical proof.
Article title in Wikipedia: Hex (board game)
Intense one. Bon voyage! That thing is an Omeric knowledge exploration boat that is sailing from since.
Crossing through the information sea-GRAPH, - the one representing the actual theorem understanding - , which
resolve itself finding the emiltonial path that solve finitely many bad abstarcion graph of the understanding of it. There's that route that lead to overcome all of them through polinomial complexity at yet no way of finding it. As finding the finitely many pages book for Babilonia that make this theorem and comment clear
easy. P=NP if N=1 or P=0. dont make it harder than it has to be, folks
im sure this will be enough to collect the prize for solving arguably the most difficult problem in math.
the day on which COVID went international omg... prophetic
You guys are going to philosophy now
he is 83, will he be able to complete all books??
P = NP , Trust me Guys .
Simpsons said it so it must be true
Well ... I see one of the issues with the definition of the NP class. The "guessing" stage of NDTM does not say ANYTHING about a potentially existing algorithm - the whole NP concept is based on polynomial VERIFICATION of that guess. So NDTM is not helping in practical solubility of a problem - it is an artificial construct, and the rest of the NP (completeness) theory (polynomial reducibility, Ladner's theorem etc.) just follows from that NP concept ...
let N=1
(x) both sides by P
PN = P
=> P = NP
Q.E.D
Where's my million dollars?
let P=0
@@asdfsolider I suppose that if there were zero extant polynomial-time algorithms, your intuition would be correct. So congratulations on proving a special case.
If you have not read Art of Computer Programming all volumes front to end then you are bad.
I'm not in this field... What is "P" and what is "NP" anyways?
In electronics, N and P define how semiconductor materials are doped, i.e. NPN or PNP transistors. But this obviously has nothing to do with what they are talking about...
Can anyone point me in the right direction please?
It’s algorithm complexity. P refers to polynomial time. NP means non polynomial.
@@hashkenhabib NP means *nondeterministic* polynomial (time). It is a class of problems which includes ones that are considered to be "diffucult" to solve as there are no quick ways to find a solution for the given problem.
Modern web cryptography relies on that fact. As opposed to P, polynomial time, problems, which have a solution in polynomial (e.g. more/less fast) time.
Correct me if i'm wrong.
P means "solvable in polynomial (as opposed to exponential) time". That means that the size of the calculation you have to do, doesn't blow exponentially up as you are trying to solve larger and larger problems.
NP means "solvable nondeterministically in polynomial time". Let's see what the "nondeterministically" means here: imagine that you had a magical supercomputer that could try *each possible way for the solving algorithm to run*, that is, every time you have a choice before you when executing the algorithm, you are allowed to calculate those choices *in parallel*, instead of first calculating the other and then another. In that case, you would find the solution in polynomial time.
This essentially reduces to something of a "tree search problem". There is a branching tree of possibilities, and the count of the three "leaves" is exponentially sized wrt. the input, but each path from the root is polynomial wrt. the input. If you are allowed to try each path from the root to the leaves in parallel, you can find the answer quickly. But if not, you have to try each possibility. NP has also the property that once you know an answer, you are able to *verify* it in polynomial time.
*Wired: P vs NP Explained in 3 levels of difficulty*
If you can solve one NP-complete problem in polynomial time, then you have effectively solved all solved all problems solvable by computers with some sort of algorithm in polynomial time. The implications of solving such a one a vast. AI would become obsolete in many cases where it is currently used.
#P=#Q knuth volume 4. The number of models equals the number of valid quantifications.
All Ps are NP anyway... P is a subset of NP
i saw a movie once based on the premise that a bunch of math whizzes figured out p=np and i was totally disappointed that they somehow didn't manage to make it massively entertaining as a movie, though it wasn't really all that bad. how was such a thing possible. did manage to watch the whole thing anyway.
oh right it was this one ua-cam.com/video/6ybd5rbQ5rU/v-deo.html
@Dick Bird Looks pretty interesting! I think I’ll check it out!
The artificial intelligence singularity will prove p=np
Cool!
I'm glad I aced my graph theory class, otherwise this would be like chinese to me
Weird flex, but ok...
Alexo360, can you link to what you think are the best descriptions of the key intuitions and paths from those to applications and formal properties?
@@tricky778 Google it
@@user-me7hx8zf9y why are you issuing commands to me? Why do you even think google will tell me what might have helped alexo360 ace his graph theory class?
@@tricky778 "issuing commands" lol, way to assume.
I'm telling you that if you want a reliable source for advice on how to perform well in a graph theory class to do your own research.
Perhaps my colloquialism was in poor taste and hurt your feelings, so sorry if that's the case.
Anyone wants to see sentdex on this podcast?
A SIMPLE problem 😏😏😏
P != NP
I’m willing to bet my left testicle and my mother on that.
If P=NP creativity does not exist.
Why do you think it exists in the first place?
Now I hope someone proofs P=NP
I absolutely agree. P = NP would esentially mean "If there is a polynomial time algorithm for verifying a solution to a problem, there is also a polynomial time algorithm for finding the solution." But that seems contrary to how much effort is required in creative work.
For example, it is easy to verify if a piece of music sounds good (i.e. whether it sounds harmonious), but it is difficult to actually make good music.
@@philipcervenjak2493 Difficult for someone who had never made music (or any creative work), to be more precise. Once you "tune in" and understand how to make it, you more or less do it automatically. There are generative adversarial networks that can generate decent music, images, etc. and they do it automatically by understanding the mechanics behind these processes. (www.wikiwand.com/en/Generative_adversarial_network)
Of course they are hardly "good" (whatever that means, its a relative term anyways), but that is not surprising, since they're just a piece of software that isn't doing that much at all.
Still, there is absolutely, and a repeat - absolutely no reason for someone to believe that this is completely impossible.
PS: Well, actually when I come to think about it - there is a reason for someone to believe its impossible - arrogance. :D
@@dimomarkov8937 I'm not an expert in machine learning or anything, but I'm not convinced that generative adversarial networks in their current state actually "understand the mechanics behind these processes." Could you elaborate on that or link to some articles about that? Thanks :).
But the thing about making art is that most people can appreciate (verify) art very efficiently, but it takes a lot of effort to figure out what people will appreciate. It appears that the only reason people become efficient at making art is that they have memorised what has worked best in the past, so they (usually) don't need to go through a trial-and-error process to make new art. For example, pretty much all musicians know that ending a song with a cadence like IV-V-I sounds good. But it's not because we have some algorithm that tells us that directly, but because we found it through trial-and-error and then verified it after hearing it.
So it seems like the GANs you mentioned are fundamentally doing the same thing as people, by copying patterns that we have already found (although you might correct me on that).
I should clarify, I'm not 100% certain that it is impossible to make good, new music efficiently (or that P != NP for that matter), I'm just saying that all the evidence suggests it is impossible.
I found the explanation too vague to be pleasurable, and even if true doesn't change a whole lot in terms of practicality...
P = NP seems too vaguely defined, involving nondeterministic Turing machines. Nondeterministic?! What the heck is that? A random process? It doesn't compute.
p vs np is very well defined tho? Nondeterministic Turing machines just means it‘s a turing machina that instead of a transition function, has a transition relation, meaning for one element of the alphabet and one state there can be multiple ways to continue the computation.
It certainly isn't. Deterministic Turing machines can only perform one operation if multiple are available to it. Nondeterministic ones are allowed to check each path simultaneously. It's definitely "hard" CS, in that these types of objects exist only as proof constructs and thus are idealized, but they are well distinguished and easily differentiable if one understands the requirements.
Chess is a pretty good example of an NP problem. If we had an NDTM, we would probably have found the "perfect game" for Chess, as any time a player made a move, the NDTM could simply check all possible responses simultaneously, instead of the tree pruning methods we use today. Cryptography is another great example, and one with practical applications.
@@true7563 Why not let NP stand for non-polynomial instead of non-deterministic? That seems like a more classical definition to me.
@@jakobwachter5181 Why not let NP stand for non-polynomial instead of non-deterministic? That seems like a more classical definition to me.
@@Anders01 There exist such classifications (albeit more rigorously defined), referred to by other names; see en.wikipedia.org/wiki/EXPTIME for an example. But to generally answer your question, it's because NP problems exist in a bubble that doesn't simply include "all other solvable problems"; there are plenty of problems solvable in non-polynomial time that are not in NP. It's a little less binary than these comments (including mine, admittedly), and public press on the problem would have one believe.
Can I communicate you in important thing that will change computer science 180 degree ?
I can solved np problem .
A man who can't speak... 🇹🇷🇹🇷🇹🇷 Top I guess
1:40 seems like a smart fella. To bad we have to cancel him now and ignore anything useful he has to offer 😉(🤔 why does the black player have to go from bottom to top?)
This guy was one of my heroes growing up. Thanks for all your work on the show, Lex.