What P vs NP is actually about

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] [this video]

> 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. [this video]