✳flâneur — a map of the web's best reading

What P vs NP is actually about – Vasek Rozhon's blog

vasekrozhon.wordpress.com · 4,640 words · saved by 1 readers

We recently made a Polylog video about the P vs NP problem. As usual, our goal was to present an underrated topic in a broadly understandable way, while being slightly imprecise and leaving out the messy technical details. This post is where I explain those details so that I can sleep well at night. The main point of the video was to present P vs NP from a somewhat unusual perspective. The most common way to frame the question is: “If you can efficiently verify a solution to some problem, does that mean you can efficiently solve it?” Our video explored a different framing: “If you can efficiently compute a function , is there an efficient way to compute ?” If you formalize both of these questions, they’re mathematically equivalent, and they’re also equivalent to the question “Can we efficiently solve the Satisfiability problem?” (as proven in a later section) I think that the framing with inverting a function is quite underrated. It’s extremely clean from a mathematical perspective an

Václav Rozhoň Uncategorized August 18, 2024 October 6, 2024 We recently made a Polylog video about a nonstandard way of understanding the P vs NP problem. As usual, our goal was to present an underrated idea in a broadly understandable way, while being slightly imprecise and leaving out the messy technical details. This post is where I explain those details so that I can sleep well at night. It does not make much sense to read this post without watching the video. EDIT: At the bottom, I added replies to some more common questions commenters asked in the YouTube chat. The main point of the vide

Explore this link on the map →

related reading