>>11387381Well, I'm listening to the P vs NP part of this interview
https://www.youtube.com/watch?v=2BdBfsXbST8When Knuth talked about classification of graphs, he spoke of classes of graphs that are closed under taking minor (shrinking edge to a vertex or deleting edge), one such class is planar graphs, but the description of such classes is clearly complicated, so kinda analogous to NP problem
Then he mentioned Robertson Seymour theorem
https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem which tells you for any such class there is a finite list of graphs that can serve as a test, if it's not in the class, you can shrink it down to one in that list of bad minimal graph. When the class is planar, the list simply contains two graphs K(5) - everyone among five neighbors or K(3,3) - the connecting 3 utilities to 3 houses without crossing meme problem on sci
1:04:00 this dude asked "why do you bring up this theorem" lol obviously the finite list of bad minors is analogous to the finite exponents in a hypothetical algorithm to solve an NP problem, it's finite but it could be 2, 20 or 20000 so it might not be useful. I'm a layman in this topic but I can see that. Knuth brought this up as a case where P is not useful in practice.
So Knuth explained the obvious, then 1:06 this dude asked again why Knuth holds the intuition that P = NP is possible when it could be so counter intuitive, this annoys me, Knuth just explained that above (he gave an example that can give an intuition as to why P = NP might not be so paradoxical) Then the interview became a bit meandering about some Aliens shit lmao, idk this guy might be a good AI coder but he doesn't strike me as particularly clever.
