Interview
Donald Knuth: P=NP | AI Podcast Clips
- Future discoveries will likely include a vast, incomprehensible number of algorithms where the existence of specific winning strategies for games like Hex or graph classification algorithms is mathematically guaranteed despite current ignorance of their forms.
- Robertson and Seymour's graph theory theorem implies that any minor-closed class of graphs possesses a polynomial-time existence algorithm defined by a finite set of forbidden minor obstructions, though identifying the complete set of these obstructions remains uncertain.
- A definitive proof establishing a finite number of bad graphs for non-planar structures is anticipated, though current knowledge of specific minor obstructions may be limited to one or two out of a potentially much larger total.
- The speaker predicts P equals NP based on the intuition that the immense space of possible algorithms contains solutions to hard problems, paralleling the search for extraterrestrial intelligence where absence of evidence does not equate to evidence of absence.
- Opposing views suggesting P cannot equal NP due to the inability of experts to find such algorithms after years of effort are noted as potentially flawed reasoning comparable to assuming aliens do not exist simply because they have not yet been found.
- A hypothetical risk scenario is presented where advanced civilizations, including those utilizing machine learning, might have discovered each other and subsequently destroyed one another.
- It is expected that algorithms will continue to exist and solve difficult problems even if humanity never discovers, understands, or is able to utilize them due to the sheer magnitude of the algorithmic possibility space.