What P vs NP is actually about

Despite being mentioned throughout the post, I don't see a link to the video in question. I saw it when it was posted a few weeks back and really enjoyed it. I would highly recommend giving it a watch, especially if the ramifications of P vs NP are new to you [1] [1] [VIDEO]

Hi, the author of the blog post here. 1) With others, I work on high-effort Youtube videos, our channel's called Polylog. We recently made a video about an underrated take on P vs NP. [1] 2) After working on the high-effort video, I always write a low-effort stream-of-consiousness-style very-much-unedited blog post where I clarify some details or explain some more esoteric stuff that did not make it into the video. The blog post you are discussing is such a blog post. So you should watch the video first and read the blog post only if you really liked the video and want to know more. :) 3) If you have any questions, I'll be happy to answer them! [1] [VIDEO]

[VIDEO] This video I think makes it obvious why that's true in a pretty intuitive way. I posted it a few days ago as a link and it never got traction. SAT is the equivalent of being able to find the inverse of _any_ function, because you can describe any function with logic gates (for obvious reasons), and any collection of logic gates that describes a function is equivalent to a SAT problem. All you need to do is codify the function in logic gates, including the output you want, and the ask a SAT solver to find the inputs that produce that output.

> What does it mean for computation to have a direction? Actually, all computation has a directionality! This is actually a subject that I get really excited about ^__^ Think about this, we have a function f, with input x, and output y. f(x) -> y We'd even use that notation! This is our direction. Now, the reverse actually gets a bit tricky. If the reverse is straightforward, our function has an inverse. But, it might not always. So our function f(x)=mx+b is invertible, because we can write x = (f(x)-b)/m (well... m can't be 0), which provides a unique solution. Every x corresponds to a unique f(x). But if instead, we have the function f(x) = x^2, this is not true! x = sqrt(f(x)), and here every f(x) corresponds to both x and -x! They are not unique. We can start adopting the language of images and preimages if you want to start heading down that route. There's a lot of interesting phenomena here and if you hadn't already guessed it, yes, this is related to the P=NP problem! An easy way to see this visually is to write down the computational circuit. Polylog actually has a really good video and will make the connection to P vs NP[0] In the context of machine learning, a Normalizing Flow would be invertible, while a diffusion model is reversible. A pet peeve of mine is that in ML people (I'm a ML researcher) call it the "inverse problem", such as GAN-Inversion, but that is a misnomer and we shouldn't propagate it... This also has to do with the naivety of these statements...[1

Yeah that's a good addition. I think often the words we use can really make things more confusing. Like I hate when people say invertible but in reference to a function that isn't bijective. Why not say reversible? (No complaints with the convention of image/preimage) Which it's very similar to the problem created by saying "one way". It just isn't one way. Going the other direction is perfectly possible but incredibly hard to find the origin. The visual metaphor I like to use for people is it's like you walk out of a room and into a hallway of doors that are all identical looking. Ignoring the fact that you could just physically turn around, it'd be very hard to figure out which one you actually came from. But maybe what I like least is that we end up having so many terms for the same general concept. It's one thing when they're discovered independently but I'm pretty confident the computer scientists that pioneered hashes were quite familiar with the mathematics and nomenclature. > inverse computation would take an intractable amount of time. On a real side note I really like this explanation of P vs NP as it explicitly talks about reversibility. [VIDEO]