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]
> 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.
It’s indeed NP-complete if edge lengths are integers or otherwise discretized. But the general traveling salesman problem has no such restriction, so you can’t finitely enumerate in the general case.
Yes. A maximal value of k can be calculated as (largest weight in the graph) times (number of nodes in the graph). At that point you can do binary search to find the smallest k for which a solution exists.
Under the assumption that the <= question can be answered in polynomial time, this entire algorithm will also complete in polynomial time.
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.
Nope, the usual way of reducing optimization problem is to ask the corresponding yes/no question - for some fixed value x, is the optimal value greater than x?
If you can solve the decision problem, you can solve the optimization problem by doing a binary search on the x.
> Not all decision problems are like that (e.g. happy net problem)
Assuming you have an oracle for any question that you know how to verify, this is very easy to reduce:
Is there a solution in which vertices {1, 4, 6} are all positive?
First, let's establish that the question is legal: presented with a working solution, we can calculate the defining constraint of the problem, and we can check the polarity of vertices 1, 4, and 6. If this problem is in NP, verifying the constraint will take at most polynomial time. If not, not, but our question can be verified in however much time it takes to calculate the constraint.
The complexity of determining a solution by getting answers to questions of this form is interesting.
Case 1: The answer is "no" for all single-vertex sets. All vertices must be negative. This cannot actually happen, because all vertices being negative is the same thing as all vertices being positive.
Case 2: All vertices may be simultaneously positive. In this case, the answer to every question will be "yes", and we'll ask one question for every vertex in the input graph, solving the problem in sublinear time.
Case 3: We need some positive and some negative vertices. By asking about single-vertex sets, we can quickly identify a vertex that can be positive, vertex A.
We will include that vertex in every subsequent question. By the time we get there, we will have already asked about zero or more other vertices and been answered "no". We need never ask about those vertices again; they have to be negative and if we include them in any set, we'll get another "no".
So, let's ask about a never-before-examined vertex, vertex B. Can {A, B} be simultaneously positive?
If not, we can toss B into the "must be negative" pile, since we know A can be positive.
If so, we can include it in our developing solution; future questions will include vertices A and B. We still never need to reexamine any vertex that has ever been included in any of our questions.
So, unless I'm missing something, in this case we'll also produce a solution using one question per vertex in the graph.
> but for this one I don’t see the point making the distinction.
The distinction between NP-complete and NP-hard has nothing to do with the distinction between yes/no questions and open-ended questions. Those are unrelated concepts.
An NP-hard problem is at least as hard as any NP problem. It might be much harder.
An NP-complete problem is NP-hard, but it's also guaranteed to be an NP problem. That's the distinction.
No, NP-Complete is only defined for decision problems. As OP specifically and correctly points out, NP hard applies to decision problems as well as search and optimization problems (and others as well).
You may review the following to clarify the distinction between the various NP complexity classes:
I for one have no idea about topology in general. I had to look up what a nice shape was... I thought it was some mathematical term.
The only thing I remember about is topology is someone telling me how it would be easier for me to untangle cables if I knew topology but alas I never learned.
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 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.
There's another term, i'm sure, because politicians use it all the time; "I never said X" when it was very heavily implied, and the listener was led down the garden path to the conclusion, only to find out the conclusion is bitter and unpleasant. The speaker can say "oh, that's your own biases/misconceptions/dogma, i never said <something extremely specific>"
I'm in the weeds here, but a simple analogy would be: "I don't like sunny days without clouds or fog." and i say "why don't you like blue skies?" and they say "i never said that" when the salient points of a sunny day with no clouds or fog are 1) there's a sun, and 2) the sky is blue.
> To me, the essence of deep learning has nothing to do with trying to mimick biological systems or something in that sense; it’s the observation that if your circuits are continuous, there’s a clear algorithmic way of inverting/optimizing them using backpropagation.
> From the perspective of someone used to algorithms like Dijkstra’s algorithm, quicksort, and so on, this declarative approach of thinking in terms of loss functions and architectures, rather than how the net is actually optimized, sounds very alien. But this is how the whole algorithmic world would look like if P equaled NP! In that world, we’d all program declaratively in Prolog and use some kind of .solve() function at the end that would internally run a fast SAT solver to solve the problem defined by our declarations.
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.
For an example of harder-than-np-complete, I was shocked to find out how hard vector reachability is after being presented with a vector reachability problem and assuming I could just look up a reasonable-time algorithm.
I incorrectly assumed it would have some basic linear algebra solution because of how simple the problem seemed.
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:
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.
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)
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 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
It's not satire. If you have some function with several inputs, the Jacobian is a matrix of all the partial derivatives of this function with respect to each input variable[1]. Since derivatives give the slope of a function, if you think about your function as being like a bumpy surface with the height at each point being the output, this matrix tells you which way (and how far) to change any input if you want to go "up" or "down" in the output.
Backpropogation is a way to optimise a neural network. You want to know how best to nudge the weights of the network to optimise some loss function, so what you do is compute the gradient (ie partial derivative) of that function with respect to each of the weights. This allows you to then tweak the weights of the function so your network gets better at whatever task you're trying to get it to learn. See [2] to understand how this works and and [3] to understand how this relates to the Jacobian, but generally if you're trying to go "downhill" in your loss function it's easy to see intuitively that knowing which way the function slopes (ie the effect of tweaking each of the weights) is important and that's what the Jacobian tells you.
The inverse of a matrix[4] and its transpose[5] are two different operations in linear algebra. Transpose turns rows into columns and columns into rows and the inverse of a matrix is a little harder to grasp maybe without background, but you could think of multiplying one matrix by the inverse of another as a little like division (since you can't actually divide matrices).[6]
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.
Is the interesting part of P vs NP (since it seems very unlikely that P = NP) the mathematical machinery that would be required to prove that P != NP? Presumably doing so would require a way to determine a lower bound for _all_ possible algorithms that solve a particular problem.
Well, it was recent, so I'm currently in the 'feedback and validation' stage. I've reached out to experts for feedback, but these things do take time.
If you have a genuine interest, and especially if you could provide feedback or warm introductions to someone who can, I'm happy to share.
You can email me at atmanthedog at Google's free email service domain. Put something HN related in the subject. *If you do, please share your mathematical background so I can better tailor a response.
I wasn't expecting to see my (uncredited) die photo of the 8008 processor in the middle of an article about P vs NP!
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...
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
> 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.
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.
If “is there a route <= k” is in NP then wouldn’t you just iteratively do this counting down from some maximal value of k?
It’s indeed NP-complete if edge lengths are integers or otherwise discretized. But the general traveling salesman problem has no such restriction, so you can’t finitely enumerate in the general case.
In the usual model of how these problems are defined, problem inputs must be represented in binary, so the edge lengths are discrete by definition.
What problem formulation do you have in mind?
No, you can easily get non-discrete lengths with simple metrics like the Euclidean metric on an integer grid.
Yes. A maximal value of k can be calculated as (largest weight in the graph) times (number of nodes in the graph). At that point you can do binary search to find the smallest k for which a solution exists.
Under the assumption that the <= question can be answered in polynomial time, this entire algorithm will also complete in polynomial time.
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.
An optimization problem can always be reduced to a decision problem of the form "Is X one of the optimal solutions to problem Y for input I?"
Nope, the usual way of reducing optimization problem is to ask the corresponding yes/no question - for some fixed value x, is the optimal value greater than x?
If you can solve the decision problem, you can solve the optimization problem by doing a binary search on the x.
That doesn't necessarily tell you what the solution with the optimal cost of x is, though.
> Not all decision problems are like that (e.g. happy net problem)
Assuming you have an oracle for any question that you know how to verify, this is very easy to reduce:
Is there a solution in which vertices {1, 4, 6} are all positive?
First, let's establish that the question is legal: presented with a working solution, we can calculate the defining constraint of the problem, and we can check the polarity of vertices 1, 4, and 6. If this problem is in NP, verifying the constraint will take at most polynomial time. If not, not, but our question can be verified in however much time it takes to calculate the constraint.
The complexity of determining a solution by getting answers to questions of this form is interesting.
Case 1: The answer is "no" for all single-vertex sets. All vertices must be negative. This cannot actually happen, because all vertices being negative is the same thing as all vertices being positive.
Case 2: All vertices may be simultaneously positive. In this case, the answer to every question will be "yes", and we'll ask one question for every vertex in the input graph, solving the problem in sublinear time.
Case 3: We need some positive and some negative vertices. By asking about single-vertex sets, we can quickly identify a vertex that can be positive, vertex A.
We will include that vertex in every subsequent question. By the time we get there, we will have already asked about zero or more other vertices and been answered "no". We need never ask about those vertices again; they have to be negative and if we include them in any set, we'll get another "no".
So, let's ask about a never-before-examined vertex, vertex B. Can {A, B} be simultaneously positive?
If not, we can toss B into the "must be negative" pile, since we know A can be positive.
If so, we can include it in our developing solution; future questions will include vertices A and B. We still never need to reexamine any vertex that has ever been included in any of our questions.
So, unless I'm missing something, in this case we'll also produce a solution using one question per vertex in the graph.
> but for this one I don’t see the point making the distinction.
The distinction between NP-complete and NP-hard has nothing to do with the distinction between yes/no questions and open-ended questions. Those are unrelated concepts.
An NP-hard problem is at least as hard as any NP problem. It might be much harder.
An NP-complete problem is NP-hard, but it's also guaranteed to be an NP problem. That's the distinction.
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.
No, NP-Complete is only defined for decision problems. As OP specifically and correctly points out, NP hard applies to decision problems as well as search and optimization problems (and others as well).
You may review the following to clarify the distinction between the various NP complexity classes:
https://en.wikipedia.org/wiki/NP-hardness#NP-naming_conventi...
From the Definition section
>A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H
Yes that is correct for decision problems.
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.
I'm willing to bet most people who knows what P vs. NP is can't explain all the 7 problems (especially Hodge conjecture) even at pop-sci level.
I can't even name all seven!
> Hodge conjecture
I for one have no idea about topology in general. I had to look up what a nice shape was... I thought it was some mathematical term.
The only thing I remember about is topology is someone telling me how it would be easier for me to untangle cables if I knew topology but alas I never learned.
Well, better start making some more YouTube videos then.
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 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.
> The word "literally" can no longer be trusted to mean "in a literal sense". It's frequently used as an intensifier.
It was ever thus.
See, for example, https://blogs.illinois.edu/view/25/96439
sounds similar to weasel words https://en.wikipedia.org/wiki/Weasel_word
There's another term, i'm sure, because politicians use it all the time; "I never said X" when it was very heavily implied, and the listener was led down the garden path to the conclusion, only to find out the conclusion is bitter and unpleasant. The speaker can say "oh, that's your own biases/misconceptions/dogma, i never said <something extremely specific>"
I'm in the weeds here, but a simple analogy would be: "I don't like sunny days without clouds or fog." and i say "why don't you like blue skies?" and they say "i never said that" when the salient points of a sunny day with no clouds or fog are 1) there's a sun, and 2) the sky is blue.
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.
> You cannot disagree with "over/under-rated" because there's no official "rating" method.
(A) That's not going to stop anyone; (B) the claim can easily be obviously false. For example, Taylor Swift is underrated.
We have here an example of problem (B); P versus NP is possibly the single most famous problem in computer science. It isn't underrated.
This is a good insight.
> To me, the essence of deep learning has nothing to do with trying to mimick biological systems or something in that sense; it’s the observation that if your circuits are continuous, there’s a clear algorithmic way of inverting/optimizing them using backpropagation.
> From the perspective of someone used to algorithms like Dijkstra’s algorithm, quicksort, and so on, this declarative approach of thinking in terms of loss functions and architectures, rather than how the net is actually optimized, sounds very alien. But this is how the whole algorithmic world would look like if P equaled NP! In that world, we’d all program declaratively in Prolog and use some kind of .solve() function at the end that would internally run a fast SAT solver to solve the problem defined by our declarations.
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.
For an example of harder-than-np-complete, I was shocked to find out how hard vector reachability is after being presented with a vector reachability problem and assuming I could just look up a reasonable-time algorithm.
I incorrectly assumed it would have some basic linear algebra solution because of how simple the problem seemed.
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 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
Thanks, it's been years since I listened to this. Now after reading about Timothy gowers I want to listen to it again.
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.
There is potentially a factorial number of solutions for NP-complete problems.
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)
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.
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
It's not satire. If you have some function with several inputs, the Jacobian is a matrix of all the partial derivatives of this function with respect to each input variable[1]. Since derivatives give the slope of a function, if you think about your function as being like a bumpy surface with the height at each point being the output, this matrix tells you which way (and how far) to change any input if you want to go "up" or "down" in the output.
Backpropogation is a way to optimise a neural network. You want to know how best to nudge the weights of the network to optimise some loss function, so what you do is compute the gradient (ie partial derivative) of that function with respect to each of the weights. This allows you to then tweak the weights of the function so your network gets better at whatever task you're trying to get it to learn. See [2] to understand how this works and and [3] to understand how this relates to the Jacobian, but generally if you're trying to go "downhill" in your loss function it's easy to see intuitively that knowing which way the function slopes (ie the effect of tweaking each of the weights) is important and that's what the Jacobian tells you.
The inverse of a matrix[4] and its transpose[5] are two different operations in linear algebra. Transpose turns rows into columns and columns into rows and the inverse of a matrix is a little harder to grasp maybe without background, but you could think of multiplying one matrix by the inverse of another as a little like division (since you can't actually divide matrices).[6]
[1] https://en.wikipedia.org/wiki/Jacobian_matrix_and_determinan...
[2] https://www.youtube.com/watch?v=Ilg3gGewQ5U
[3] https://www.youtube.com/watch?v=tIeHLnjs5U8
[4] https://math.libretexts.org/Workbench/1250_Draft_4/07%3A_Mat...
[5] https://math.libretexts.org/Bookshelves/Linear_Algebra/Funda...
[6] algebraists please don't shoot me for that.
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.
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?
It's a joke, they're doing algebra on the letters.
Is the interesting part of P vs NP (since it seems very unlikely that P = NP) the mathematical machinery that would be required to prove that P != NP? Presumably doing so would require a way to determine a lower bound for _all_ possible algorithms that solve a particular problem.
I know no one will believe this but I'm reasonably sure I proved P!=NP earlier this week.
It was very similar to a previous unsolved problem in a "haha, history repeats itself" sort of way.
This comment might have a lot more comments someday.
You might avoid common pitfalls by reading "Eight Signs A Claimed P≠NP Proof Is Wrong": https://scottaaronson.blog/?p=458.
"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
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.
Well, it was recent, so I'm currently in the 'feedback and validation' stage. I've reached out to experts for feedback, but these things do take time.
If you have a genuine interest, and especially if you could provide feedback or warm introductions to someone who can, I'm happy to share.
You can email me at atmanthedog at Google's free email service domain. Put something HN related in the subject. *If you do, please share your mathematical background so I can better tailor a response.
[dead]