Sorry, I added the credit now. Hope you don't mind it now? :)

I have to say that I find these pictures extremely aesthetical. It's crazy how the brutally powerful CPUs we have today are successors to processors created not so long ago that also, though very intricate, fit into one picture...

just in case someone is wondering.... I assume it's this little beauty

https://www.righto.com/2016/12/die-photos-and-analysis-of_24...

Thanks. I also added the link to the post now. Frankly, I did not count on people getting to the blog post in any other way than being curious after watching the video. :D

It's hardly an underrated topic. In fact, probably the most well-known from all the millennium prize problems.

Edit: presenting the problem with inverting functions is an unusual approach tho.

I think that word is in the process of being re-defined. I see it used a lot in the context of older pop music or singers/bands that are no longer at their peak.

My own pet theory is that it's an evolution of speech towards "hardened" claims that you can't easily disagree with. You cannot disagree with "over/under-rated" because there's no official "rating" method. You cannot disagree with "vibes" because the source of a vibration is impossible to determine. They both allow a speaker to make a claim without evidence.

I'm pretty sure the author is specifically referring to the framing of P vs NP used in the video, not to the problem itself, since a bit into the article they write this:

"I think that the framing with inverting a function f is quite underrated."

I love "In our time". When you said this I thought "I'll know if they're really serious if Tim Gowers[1] is one of the guests". Sure enough, he is.

The BBC also had him on (the Today programme iirc but it was a while ago) the one time to comment when someone claimed to have proved it.

[1] https://en.wikipedia.org/wiki/Timothy_Gowers

The only banter is when the producer offers tea at the end, which seems incredibly necessary to me.

"An arbitrary single solution" would be the proper answer for NP. The goal is to find some solution that the verifier accepts, like how in SAT the goal is to find some satisfying assignment for all clauses.

Informally, an example of this problem is calculus class. A kid who's interested in programming, and takes calculus, can dream up a program that computes the derivative of any expression. But now try doing that with the anti-derivative. And to be sure you can write an expression in multiple ways, but the core problem remains.

Disclosure: I was that kid. My program was a mess, but good enough for a proof of concept.

In some contexts, the inverse of a function f : A -> B is defined as a function g : B -> A such that g(f(x)) = x and f(g(y)) = y for all x,y.

In other contexts, what is meant is g : B -> 2^A such that x is in g(f(x)) for all x and f(x') = f(x) for all x' in g(f(x)). Here, g is said to produce the pre-image under f, and is a generalization of the above definition of inverse for non-injective functions.

In other contexts still, what is meant is g : B -> A such that f(g(y)) = y for all y such that there exists some x with f(x) = y. This is a different generalization called a one-sided inverse. (People probably call it a left inverse or right inverse, but I can never remember which is which because it emerges from an arbitrary notational convention.)

The article uses inverse in this third sense. "Find some input to f which would yield a given output y, if one exists."

Hi, a few commenters on Youtube also asked us this question. I just now added the last section to the blog post that discusses it. Basically, although we only show how to find one arbitrary solution, you can use this trick to also find all of them efficiently in terms of the size of the input and the number of solutions.

Idea is to add enough constraints to the function so that inverting it is non trivial (where inverts finds ANY input). Like the video said inverting multiplication with the output of 15 could yield 15 = 15 * 1, so just make the function f(a, b) = a * b where a > 1 and b > 1 for a more interesting RSA-breaking case.

Given that there is potentially an exponential number of solutions, it would be impossible to enumerate them all in anything smaller than exponential time.

I think a much closer analogy to function inversion is MCMC (or Bayesian inference in general), where we can easily compute the density p(x) of any point x, but finding the x given a p(x) is intractable. Strictly speaking it's about finding a set of x's that are distributed as p(X), not finding the x given any single density p(x), but it's close.

Relatedly, probabilistic programming was originally imagined pretty much like your second quote: you define a model, get some data, run them both through the built-in inference engine, and you get the parameters of the model likely to have produced the data. In practice though, there's no universal inference engine that works for everything (some people disagree, but they're NUTS ;) I guess pretty much for the same reason P is probably not equal to NP.

Backprop itself doesn't invert the computation, but it does give you the direction for an incremental move towards the inverse (a 'nudge' as the article puts it). That is, given a sufficiently nice function f and an appropriate loss ||f(x) - y*||^2, gradient descent wrt x will indeed recover the inverse x* = f^{-1}(y*) since that is what minimizes the loss. I assume this what the article is pointing at.

If you want to be picky, it's true that the direct analogue of continuous optimization would be discrete optimization (integer programming, TSP, etc) rather than decision problems like SAT. But there are straightforward reductions between the two so it's common to speak of optimization problems as being in P or NP even though that's not entirely accurate.

"So, for example, if you can solve some problem \Pi by running a SAT solver ten times, this doesn’t mean that you have reduced that problem to SAT— in reduction, you can only run the SAT solver once."

This is also not true.

Hi, the author of the blog post here.

The section was written horribly -- while I was talking about backpropagation, I was thinking about "what can be done in polynomial time" and there's a mismatch as you explained. Thanks and shame on me, I rewrote it.

In any case, I would recommend watching the video first, the article is just accompanied stream of consciousness for those few who really liked the video.

This is one of the many comments I see on HN where I genuinely have no idea whether it’s satire or just high-level technical talk. I assume the latter, but I don’t know enough to disprove the former

They're almost certainly not equal because solving NP in P time requires magically making exponential decisions in P time. What's interesting that it's been so hard to prove one way or the other.

I realise you're probably joking but on the off-chance you are not, P and NP are sets containing classes of algorithms. They aren't numbers. See https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pd... for a formal description of the problem.

I would recommend reading the article.

P vs NP is one of the foundational open problems in computer science.

> even I can see that N = 1 or P = 0

wat?

Exactly! In theoretical computer science, we have a lot of experience coming up with new algorithms but no idea how to prove lower bounds. So I would say that new lower-bound technique is perhaps the most interesting thing we would learn from the proof of P!=NP.

But, of course, P vs NP is clearly central to computer science and math for a bunch of other reasons, hopefully, our video provided some intuitions.

"I have discovered a truly marvelous demonstration of the proposition that P/=NP but this HN comment is too short to contain it..."

Eagerly awaiting your published proof

You might avoid common pitfalls by reading "Eight Signs A Claimed P≠NP Proof Is Wrong": https://scottaaronson.blog/?p=458.

That's fantastic if true. Make sure you check out the Clay institute's page and collect your prize.[1]

[1] https://www.claymath.org/millennium/p-vs-np/ and especially https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pd...

I don't believe you, but you can always prove me wrong and share your proof.