5 ms·

> 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

> 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.

karmakurtisaani 2y ago
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.
- theturtletalks 2y ago
  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.
  - vlovich123 2y ago
    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-differences-between-np-np-complete-and-np-hard#1857342 https://stackoverflow.com/questions/1857244/what-are-the-dif... https://en.m.wikipedia.org/wiki/Travelling_salesman_problem https://en.m.wikipedia.org/wiki/Travelling_salesman_problem
    - pyrale 2y ago
      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.
      - Maxatar 2y ago
        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?"
        alex_smart 2y ago
        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.
        Delk 2y ago
        That doesn't necessarily tell you what the solution with the optimal cost of x is, though.
        pyrale 2y ago
        You can always reduce anything to anything, but in this case, the reduction is relevant because it only adds a polynomial factor. Showing that a problem can be reduced to another one in polynomial time is core to proving np-completeness. That means that tsp and tso-opt are in the same ballpark of complexity. The reason tsp-opt isn't called np-complete isn't related to its complexity, but to the fact that only decision problems get to be called that. As I said, there are problems where the decision problem and the optimization problem are completely unrelated in terms of complexity, but tsp isn't one of those.
      - thaumasiotes 2y ago
        > 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.
    - alex_smart 2y ago
      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.
      - Maxatar 2y ago
        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_convention https://en.wikipedia.org/wiki/NP-hardness#NP-naming_conventi...
        deleted 2y ago
        [deleted]
        alex_smart 2y ago
        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
        Maxatar 2y ago
        Yes that is correct for decision problems.
    - krick 2y ago
      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.
    - kenjackson 2y ago
      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?
      - thaumasiotes 2y ago
        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.
      - oefrha 2y ago
        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.
        atq2119 2y ago
        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?
        oefrha 2y ago
        No, you can easily get non-discrete lengths with simple metrics like the Euclidean metric on an integer grid.
        thaumasiotes 2y ago
        In the general case, you just have a big list of edge weights, which means you have to be able to write the edge weights down. If you want to represent the problem as a bunch of points in a Euclidean plane with free travel, that's a different (and easier) problem. And even then, while it might take an infinite number of steps to specify the answer at infinite resolution, it will only take a finite number of steps to specify the answer at any level you're capable of writing down.
- KPGv2 2y ago
  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.
  - karmakurtisaani 2y ago
    Well, better start making some more YouTube videos then.
  - raincole 2y ago
    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.
    - thanksgiving 2y ago
      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.
gosub100 2y ago
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.
- tgv 2y ago
  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.
  - ttctciyf 2y ago
    > 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 https://blogs.illinois.edu/view/25/96439
    - tgv 2y ago
      That's a bad case of gotcha linguistics.
      - deleted 2y ago
        [deleted]
- magicalhippo 2y ago
  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.
- genewitch 2y ago
edanm 2y ago
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."
- vasekrozhon 2y ago
  Yes! We are not trying to claim that P vs NP is underrated in the video, just the bit with interpreting it as a question about inverting functions. I think using "underrated" is justified, I talked with a bunch of people about this topic and it was a new way of looking at it for a lot of them. Of course, using the title "What P vs NP is actually about" is a bit of a stretch -- "Interesting take on P vs NP" would be more honest.
  - edanm 2y ago
    Totally justified, I hadn't thought about that framing of it myself. I think it's just that the first time you use underrated, it seems to be referring to the problem itself, not to your specific take. With the video as context, or even just reading a few sentences in, the meaning is clearer.

karmakurtisaani 2y ago

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.

theturtletalks 2y ago
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.
- vlovich123 2y ago
  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-differences-between-np-np-complete-and-np-hard#1857342 https://stackoverflow.com/questions/1857244/what-are-the-dif... https://en.m.wikipedia.org/wiki/Travelling_salesman_problem https://en.m.wikipedia.org/wiki/Travelling_salesman_problem
  - pyrale 2y ago
    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.
    - Maxatar 2y ago
      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?"
      - alex_smart 2y ago
        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.
        Delk 2y ago
        That doesn't necessarily tell you what the solution with the optimal cost of x is, though.
      - pyrale 2y ago
        You can always reduce anything to anything, but in this case, the reduction is relevant because it only adds a polynomial factor. Showing that a problem can be reduced to another one in polynomial time is core to proving np-completeness. That means that tsp and tso-opt are in the same ballpark of complexity. The reason tsp-opt isn't called np-complete isn't related to its complexity, but to the fact that only decision problems get to be called that. As I said, there are problems where the decision problem and the optimization problem are completely unrelated in terms of complexity, but tsp isn't one of those.
    - thaumasiotes 2y ago
      > 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.
  - alex_smart 2y ago
    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.
    - Maxatar 2y ago
      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_convention https://en.wikipedia.org/wiki/NP-hardness#NP-naming_conventi...
      - deleted 2y ago
        [deleted]
      - alex_smart 2y ago
        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
        Maxatar 2y ago
        Yes that is correct for decision problems.
  - krick 2y ago
    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.
  - kenjackson 2y ago
    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?
    - thaumasiotes 2y ago
      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.
    - oefrha 2y ago
      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.
      - atq2119 2y ago
        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?
        oefrha 2y ago
        No, you can easily get non-discrete lengths with simple metrics like the Euclidean metric on an integer grid.
      - thaumasiotes 2y ago
        In the general case, you just have a big list of edge weights, which means you have to be able to write the edge weights down. If you want to represent the problem as a bunch of points in a Euclidean plane with free travel, that's a different (and easier) problem. And even then, while it might take an infinite number of steps to specify the answer at infinite resolution, it will only take a finite number of steps to specify the answer at any level you're capable of writing down.
KPGv2 2y ago
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.
- karmakurtisaani 2y ago
  Well, better start making some more YouTube videos then.
- raincole 2y ago
  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.
  - thanksgiving 2y ago
    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.

gosub100 2y ago

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.

tgv 2y ago
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.
- ttctciyf 2y ago
  > 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 https://blogs.illinois.edu/view/25/96439
  - tgv 2y ago
    That's a bad case of gotcha linguistics.
    - deleted 2y ago
      [deleted]
magicalhippo 2y ago
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.
genewitch 2y ago

edanm 2y ago

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."

vasekrozhon 2y ago
Yes! We are not trying to claim that P vs NP is underrated in the video, just the bit with interpreting it as a question about inverting functions. I think using "underrated" is justified, I talked with a bunch of people about this topic and it was a new way of looking at it for a lot of them. Of course, using the title "What P vs NP is actually about" is a bit of a stretch -- "Interesting take on P vs NP" would be more honest.
- edanm 2y ago
  Totally justified, I hadn't thought about that framing of it myself. I think it's just that the first time you use underrated, it seems to be referring to the problem itself, not to your specific take. With the video as context, or even just reading a few sentences in, the meaning is clearer.