What P vs NP is actually about
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 and highlights the fundamental nature of the question. We can also easily view the more common verifier-formulation of P vs NP as a special case of this one, once we realize that inverting a checker algorithm and “running it backward from YES” solves the problem that the checker verifies.
