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]
I just skimmed the article and didn't watch the video, but the bit about backpropagation is just wrong. Backpropagation doesn't compute an inverse of the jacobian, it computes its transpose. (although a similar idea to backpropagation could possibly be used to compute an inverse of several reversible layers, but that's not typically how neural networks work)
> 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
Interesting post but not sure why the author calls it underrated. It seems to get a fare share of attention and love amongst those that care about such things.
Interestingly the shortest route question of the salesman problem (which is what everyone associates it with) is NP-hard and thus not necessarily even within NP. P vs NP is specifically about P vs NP complete whereas NP-hard is problems that are at least as hard as NP-complete but need not be in NP nor decision problems. So make sure you give the “is there a route <= k” version because the much more common “find the shortest route version” is not NP.
Somebody really should come up with better names. I know for a fact I knew the difference once, but right now I cannot even remember what it was without clicking the link. Surely many people who heard about this problem (and that's a lot of people, it's about as pop-mathy as it gets) don't even suspect these aren't synonymous.
In this case np-complete and np-hard are closely linked: the optimization problem can be reduced to the decision version. Not all decision problems are like that (e.g. happy net problem), but for this one I don’t see the point making the distinction.
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.
Might be the clickbait treadmill, indeed, or algospeak. But it doesn't need an objective meaning to be treated that way. The word "literally" can no longer be trusted to mean "in a literal sense". It's frequently used as an intensifier.
Framing this as inverting a function is interesting, but raises a question, since any function that maps multiple inputs to the same output is not invertible.
For example, let's say we invert a checker algorithm and "run it backward from YES". Does that find an arbitrary single solution? Does it find all solutions? What if there are an infinite number of solutions?
"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."
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.
BBC "in our time" radio show did an outstanding episode on the topic. As usual it had an amazing calibre of guests but a totally understated style. Also no long pointless intro full of terrible banter or lengthy bullet list of what will be discussed.
I wish podcasts could follow this example:
26 comments:
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] https://www.youtube.com/watch?v=6OPsH8PK7xM
I wasn't expecting to see my (uncredited) die photo of the 8008 processor in the middle of an article about P vs NP!
I just skimmed the article and didn't watch the video, but the bit about backpropagation is just wrong. Backpropagation doesn't compute an inverse of the jacobian, it computes its transpose. (although a similar idea to backpropagation could possibly be used to compute an inverse of several reversible layers, but that's not typically how neural networks work)
> 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
Interesting post but not sure why the author calls it underrated. It seems to get a fare share of attention and love amongst those that care about such things.
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.
Personally, I think it's fair to say all Millennium Prize problems are underrated because 99.9% of humans alive have no idea what that is.
Well, better start making some more YouTube videos then.
I was introduced to the P vs. NP problem via the traveling salesman problem and honestly seems like easiest way to explain it to people.
Interestingly the shortest route question of the salesman problem (which is what everyone associates it with) is NP-hard and thus not necessarily even within NP. P vs NP is specifically about P vs NP complete whereas NP-hard is problems that are at least as hard as NP-complete but need not be in NP nor decision problems. So make sure you give the “is there a route <= k” version because the much more common “find the shortest route version” is not NP.
https://stackoverflow.com/questions/1857244/what-are-the-dif...
https://en.m.wikipedia.org/wiki/Travelling_salesman_problem
Somebody really should come up with better names. I know for a fact I knew the difference once, but right now I cannot even remember what it was without clicking the link. Surely many people who heard about this problem (and that's a lot of people, it's about as pop-mathy as it gets) don't even suspect these aren't synonymous.
To whatever extent the shortest route question is not in NP, it is also not NP-hard.
Both NP and NP-hard are defined for the class of decision problems.
In this case np-complete and np-hard are closely linked: the optimization problem can be reduced to the decision version. Not all decision problems are like that (e.g. happy net problem), but for this one I don’t see the point making the distinction.
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.
Might be the clickbait treadmill, indeed, or algospeak. But it doesn't need an objective meaning to be treated that way. The word "literally" can no longer be trusted to mean "in a literal sense". It's frequently used as an intensifier.
Yeah was gonna say the same. As seen on a recent video: "Blondie is so underrated!"...
Though I guess for a lot of young people it feels like that, with none of their friends talking about such bands.
Framing this as inverting a function is interesting, but raises a question, since any function that maps multiple inputs to the same output is not invertible.
For example, let's say we invert a checker algorithm and "run it backward from YES". Does that find an arbitrary single solution? Does it find all solutions? What if there are an infinite number of solutions?
"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."
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.
BBC "in our time" radio show did an outstanding episode on the topic. As usual it had an amazing calibre of guests but a totally understated style. Also no long pointless intro full of terrible banter or lengthy bullet list of what will be discussed. I wish podcasts could follow this example:
https://www.bbc.co.uk/programmes/b06mtms8
I've never understood why this problem is considered so difficult. I'm not a fancy schmancy computer scientist but even I can see that N = 1 or P = 0.
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?
It's a joke, they're doing algebra on the letters.