Chapter
Non-constructive proofs and the complexity class of sharp P.
1:23:00 - 1:30:10 (07:09)
Counting the number of valid solutions to constraint satisfaction problems could enable non-constructive proof of algorithms that are hard to find otherwise. Such problems belong to the complexity class known as sharp P (#P).
Clips
The concept of proving NP completeness through non-constructive methods is discussed, though traditionally an algorithm would be needed to prove such a thing.
1:23:00 - 1:28:05 (05:04)
Summary
The concept of proving NP completeness through non-constructive methods is discussed, though traditionally an algorithm would be needed to prove such a thing. The Riemann hypothesis and the Poincaré conjecture, one of the seven Millennium Prize Problems, are also mentioned.
ChapterNon-constructive proofs and the complexity class of sharp P.
Episode#130 – Scott Aaronson: Computational Complexity and Consciousness
PodcastLex Fridman Podcast
The constraints imposed on solving complex problems and their solutions can be categorized in problem-solving models such as Sharp P and P Space.
1:28:05 - 1:30:10 (02:04)
Summary
The constraints imposed on solving complex problems and their solutions can be categorized in problem-solving models such as Sharp P and P Space. Solving problems in NP is easier than solving trigonometric problems in P space, which involve constraints-like finding winning positions in chess.