5 ms·

The joke ignores the obvious though: many instances of NP problems can be solved completely with our current machines in very short time periods.

valarauca1 11y ago
The joke also ignores that most limited BSP are solvable in P space. But then nearly all jokes temporarily suspend reality for several sentences, or paragraphs. In fact one theory postulates that humor is the human reaction when we're confronted by facts that lie outside of our present psychological scheme's ability to comprehend as possible. Generally speaking in depth analysis of jokes is a futile affair. This sentiment is often expressed via the phrase, "I'm only joking."
ColinWright 11y ago
By the way, I was reading an old comment of yours[0] and although I can't answer there because it's too old, I do have an answer for you ... You question was: If it were possible to efficiently solve a large NP-complete problem, the solution to which real-world problem would have the largest positive impact? As a single problem, graph three coloring is one that has an immediate impact in a genuine real-world problem. You give me a number to factor, and I can produce a graph such that if you 3-color it, I can read off the factors of the given number. Similarly I can solve the discrete log problem. It's not yet clear that I can do the same for elliptic-curve cryptography, but if you could graph three color efficiently, you've directly and practically broken most existing cryptosystems. Email me if you want more details. [0] https://news.ycombinator.com/item?id=8750542 https://news.ycombinator.com/item?id=8750542
- jsprogrammer 11y ago
  Thanks for responding here. I probably would have never seen the comment otherwise. (Perhaps why commenting on old threads is disabled?) Certainly cryptosystems could be broken, but I'm not sure of the immediate positive impact of that. It would seem that it could be dangerously disruptive to drop such an algorithm. I'm more interested in the "We know there are all these really hard problems and how to solve them, but we just don't have the computational power to solve them" aspect that typically comes along with P v. NP discussions. I understand many of the theoretical problems (3-coloring, subset sum, subgraph isomorphism, etc), but I want to know what practical problems do we have that we don't have good solutions to, simply because NP problems are too hard for us to compute.
  - ColinWright 11y ago
    > I probably would have never seen > the comment otherwise. You might want to look into HN Notify[0] > I'm more interested in the "We know > there are all these really hard > problems and how to solve them, but > we just don't have the computational > power to solve them" aspect that > typically comes along with P v. NP > discussions. OK, that makes it clear that I really don't know what you're asking for. The point is that there are all these problems such that the algorithms we have are exponential, which makes them infeasible. In that sense we don't know how to solve them. Why do you claim we do know how to solve them? > I understand many of the theoretical > problems (3-coloring, subset sum, > subgraph isomorphism, etc), but I want > to know what practical problems do we > have that we don't have good solutions > to, simply because NP problems are too > hard for us to compute. ?? What do you mean when you say these are theoretical? If we can 3-color then we can perform better packing, better scheduling, better layouts for processors, we can break crypto-systems, in what sense are these not practical? Can you give me any example of anything you would call a practical problem? [0] http://hnnotify.com/ http://hnnotify.com/
    - jsprogrammer 11y ago
      >OK, that makes it clear that I really don't know what you're asking for. The point is that there are all these problems such that the algorithms we have are exponential, which makes them infeasible. In that sense we don't know how to solve them. Why do you claim we do know how to solve them? I claim we can solve them, because we know the basic algorithm that will solve any particular problem given enough time and space: brute-force search and verify. >What do you mean when you say these are theoretical? There is the theoretical, "This entire class of problems is hard.", NP problem and there is the, "Provide me with a 3-coloring of this specific graph", NP problem. I claim that while it is widely believed that we cannot solve the entire class of NP problems, we may be able to solve particular, realized instances of problems from that class. Yes, the algorithms are exponential, but if you choose your parameter space appropriately, you may be able to run an exponential algorithm in a reasonable amount of time and space. So, there are parameters for algorithms that we can compute solutions for, but we are still limited to the amount of physical computational ability that we can control. This puts limits on which particular problems we can solve. >If we can 3-color then we can perform better packing, better scheduling, better layouts for processors, we can break crypto-systems, in what sense are these not practical? Only in the sense that I'm looking for a specific packing problem. For example, here are the dimensions and locations of UPS's fleet. Here are the dimensions, locations, and destinations of the packages. Give me the optimal routes. Practically, you'd probably want to model and solve failure modes as well to find the most "robust" route. >better packing, better scheduling, better layouts for processors What you are referring to here, I have been referring to as "theoretical". Optimizing UPS may or may not have much tangible benefit, depending on how close their current solutions are to the optimal. My question is asking: solving which particular problem would provide the most benefit? >Can you give me any example of anything you would call a practical problem? That is my question. :) But, a toy example would be roughly (though could could possibly be attacked another way): Provide a subset of [-12,30,7,9,-84,24,1,8,3,-5,2] that sums to 0. Edit: Thanks for the link. I'm not sure if I want an email from every reply that I get here...but I'll think about it.

valarauca1 11y ago

The joke also ignores that most limited BSP are solvable in P space. But then nearly all jokes temporarily suspend reality for several sentences, or paragraphs. In fact one theory postulates that humor is the human reaction when we're confronted by facts that lie outside of our present psychological scheme's ability to comprehend as possible. Generally speaking in depth analysis of jokes is a futile affair. This sentiment is often expressed via the phrase, "I'm only joking."

ColinWright 11y ago

By the way, I was reading an old comment of yours[0] and although I can't answer there because it's too old, I do have an answer for you ... You question was: If it were possible to efficiently solve a large NP-complete problem, the solution to which real-world problem would have the largest positive impact? As a single problem, graph three coloring is one that has an immediate impact in a genuine real-world problem. You give me a number to factor, and I can produce a graph such that if you 3-color it, I can read off the factors of the given number. Similarly I can solve the discrete log problem. It's not yet clear that I can do the same for elliptic-curve cryptography, but if you could graph three color efficiently, you've directly and practically broken most existing cryptosystems. Email me if you want more details. [0] https://news.ycombinator.com/item?id=8750542 https://news.ycombinator.com/item?id=8750542

jsprogrammer 11y ago
Thanks for responding here. I probably would have never seen the comment otherwise. (Perhaps why commenting on old threads is disabled?) Certainly cryptosystems could be broken, but I'm not sure of the immediate positive impact of that. It would seem that it could be dangerously disruptive to drop such an algorithm. I'm more interested in the "We know there are all these really hard problems and how to solve them, but we just don't have the computational power to solve them" aspect that typically comes along with P v. NP discussions. I understand many of the theoretical problems (3-coloring, subset sum, subgraph isomorphism, etc), but I want to know what practical problems do we have that we don't have good solutions to, simply because NP problems are too hard for us to compute.
- ColinWright 11y ago
  > I probably would have never seen > the comment otherwise. You might want to look into HN Notify[0] > I'm more interested in the "We know > there are all these really hard > problems and how to solve them, but > we just don't have the computational > power to solve them" aspect that > typically comes along with P v. NP > discussions. OK, that makes it clear that I really don't know what you're asking for. The point is that there are all these problems such that the algorithms we have are exponential, which makes them infeasible. In that sense we don't know how to solve them. Why do you claim we do know how to solve them? > I understand many of the theoretical > problems (3-coloring, subset sum, > subgraph isomorphism, etc), but I want > to know what practical problems do we > have that we don't have good solutions > to, simply because NP problems are too > hard for us to compute. ?? What do you mean when you say these are theoretical? If we can 3-color then we can perform better packing, better scheduling, better layouts for processors, we can break crypto-systems, in what sense are these not practical? Can you give me any example of anything you would call a practical problem? [0] http://hnnotify.com/ http://hnnotify.com/
  - jsprogrammer 11y ago
    >OK, that makes it clear that I really don't know what you're asking for. The point is that there are all these problems such that the algorithms we have are exponential, which makes them infeasible. In that sense we don't know how to solve them. Why do you claim we do know how to solve them? I claim we can solve them, because we know the basic algorithm that will solve any particular problem given enough time and space: brute-force search and verify. >What do you mean when you say these are theoretical? There is the theoretical, "This entire class of problems is hard.", NP problem and there is the, "Provide me with a 3-coloring of this specific graph", NP problem. I claim that while it is widely believed that we cannot solve the entire class of NP problems, we may be able to solve particular, realized instances of problems from that class. Yes, the algorithms are exponential, but if you choose your parameter space appropriately, you may be able to run an exponential algorithm in a reasonable amount of time and space. So, there are parameters for algorithms that we can compute solutions for, but we are still limited to the amount of physical computational ability that we can control. This puts limits on which particular problems we can solve. >If we can 3-color then we can perform better packing, better scheduling, better layouts for processors, we can break crypto-systems, in what sense are these not practical? Only in the sense that I'm looking for a specific packing problem. For example, here are the dimensions and locations of UPS's fleet. Here are the dimensions, locations, and destinations of the packages. Give me the optimal routes. Practically, you'd probably want to model and solve failure modes as well to find the most "robust" route. >better packing, better scheduling, better layouts for processors What you are referring to here, I have been referring to as "theoretical". Optimizing UPS may or may not have much tangible benefit, depending on how close their current solutions are to the optimal. My question is asking: solving which particular problem would provide the most benefit? >Can you give me any example of anything you would call a practical problem? That is my question. :) But, a toy example would be roughly (though could could possibly be attacked another way): Provide a subset of [-12,30,7,9,-84,24,1,8,3,-5,2] that sums to 0. Edit: Thanks for the link. I'm not sure if I want an email from every reply that I get here...but I'll think about it.