5 ms·

I don't claim to have solved P=NP nor do I claim to have an algorithm. The word "theoretical" was only used to distinguish between problems and instances. The

I don't claim to have solved P=NP nor do I claim to have an algorithm. The word "theoretical" was only used to distinguish between problems and instances. The question is, "Solving which instances, in which order, would lead to the most positive outcomes?", where "positive outcomes" is intentionally ill-defined so that the answerer can inject their own perspective as well. Imagine you can solve any NP-complete instance of a given size (even with a P-time/space algorithm there would still be limits on the size of problem that could be solved in a given time with a given machine). Sure, maybe you could break most crypto-systems and seize control of very electronic bit of currency (why wait for someone to decide to give it to you?). It's not clear to me that would necessarily be a productive use of the algorithm. Instead, I'm looking for instances where a solution would directly lead to less suffering. For example, with a given sub-optimal route, drivers must spend X amount of time. With the optimal route, drivers only spend X - Y time. >Is that what you're asking? Not exactly. While it would be nice to have a scheme for validating algorithms and I would have some use for it, I'm actually more interested in the instances that need solving. I think the question is interesting in that it could provide a base of problems for researchers to play/test with. These problems have been developed in the literature, but as far as I know, there is no easy to access repository of them. I think the question is also interesting because people often talk about how great the world would be if P=NP and we could easily solve NP problems. However, this talk is typically only "theoretical" (about problems and not instances). If someone can claim the world would be better off with faster solutions, they should be able to provide an instance whose solution would lead to a better world.

ColinWright 11y ago
> I don't claim to have solved P=NP > nor do I claim to have an algorithm. But you know someone who claims to be able to solve subset-sum problems quickly. I have a graph to 3-color, I wonder if I should convert it into a subset-sum problem for them to solve. That would take some time, and I'm pretty sure it won't be worth it. I'll have a think. > The word "theoretical" was only used > to distinguish between problems and > instances. OK, noted. > The question is, > "Solving which instances, in which order, > would lead to the most positive outcomes?", > where "positive outcomes" is intentionally > ill-defined so that the answerer can inject > their own perspective as well. Now I'm starting to get some idea of what you're asking. Give me some time (I'm about to go into a string of meetings) and I'll see if I can phrase it differently to see if I really do know what you're asking. > I think the question is also interesting > because people often talk about how great > the world would be if P=NP and we could > easily solve NP problems. Actually, people mostly talk about how the world would be much better if NP != P. > However, this talk is typically only > "theoretical" (about problems and not > instances). Of course - people are researching how to solve the problems, specific instances are specific instances, whereas the research challenge is algorithms for the problem. > If someone can claim the world would > be better off with faster solutions, > they should be able to provide an > instance whose solution would lead > to a better world. Why? Often we don't know the true benefits of an advance in science or technology until well after it's done, dusted, commercialized, and in the hands of ordinary people. Given that there currently are no ways to solve big, hard instances of NPC problems, why should people bother to find specific instances?
- jsprogrammer 11y ago
  >Actually, people mostly talk about how the world would be much better if NP != P. I know I've seen some arguments stating as such. If you know of a well-founded one, I'd be interested in reading it. Personally, I don't know or have a strong opinion. Seems like either could be viewed as "better" in some way. >But you know someone who claims to be able to solve subset-sum problems quickly. I have a graph to 3-color, I wonder if I should convert it into a subset-sum problem for them to solve. That would take some time, and I'm pretty sure it won't be worth it. I'll have a think. Well, I actually wrote up some tests for him and he ran his algorithm against it. I also gave him a ~10MB text file containing a very large list of integers (I forget the range at the moment. I could find it if you'd like, but I'm not sure how meaningful it is.) with a randomly selected target sum. He provided the solution (which I have not verified) in ~6-9 months. He also ran through many thousands of problem instances (subset sum...in JSON arrays) with varying parameters (number of integers; range of integers) over the course over several days. I made a rudimentary plot of the parameters and timings and in my very limited analysis, it did appear that there was a sub-exponential trend (at least for the instances that he provided solutions to [:)]). I've been searching for the results (all instances, solutions, and timings) that I had collected from the test machine, but I haven't been able to find them yet. However, all of the test code is on GitHub and packaged into Docker containers for easy deployment of the test server and basic visualization of the results. I'd guess he (the person who claims a P=NP proof and sub-exponential-time subset sum solver) would be willing to run his algorithm against the test server again.
  - ColinWright 11y ago
    >> Actually, people mostly talk about how >> the world would be much better if NP != P. > Seems like either could be viewed as > "better" in some way. Indeed, it depends on your internal axioms about "better". I don't have strong feelings either way either, and my feelings don't affect what's true and what isn't. The problem is open, remains open, and we deal with what's in front of us. >> But you know someone who claims to be >> able to solve subset-sum problems quickly. > ... He also ran through many thousands > of problem instances ... with varying > parameters ... it did appear that there > was a sub-exponential trend ... Unfortunately that means exactly nothing. The whole point is that for many (perhaps most) problems, the proportion of hard instances gets vanishingly small, and yet those are the ones that we often need to solve. Showing a sub-exponential trend for randomly chosen instances, or worse, instances he's chosen to show you, is no evidence at all. >> I have a graph to 3-color, I wonder if >> I should convert it into a subset-sum >> problem for them to solve. > I'd guess he (the person who claims a > P=NP proof and sub-exponential-time > subset sum solver) would be willing > to run his algorithm ... Perhaps that would be interesting. I'll look into how easy the conversion might be.

ColinWright 11y ago

> I don't claim to have solved P=NP > nor do I claim to have an algorithm. But you know someone who claims to be able to solve subset-sum problems quickly. I have a graph to 3-color, I wonder if I should convert it into a subset-sum problem for them to solve. That would take some time, and I'm pretty sure it won't be worth it. I'll have a think. > The word "theoretical" was only used > to distinguish between problems and > instances. OK, noted. > The question is, > "Solving which instances, in which order, > would lead to the most positive outcomes?", > where "positive outcomes" is intentionally > ill-defined so that the answerer can inject > their own perspective as well. Now I'm starting to get some idea of what you're asking. Give me some time (I'm about to go into a string of meetings) and I'll see if I can phrase it differently to see if I really do know what you're asking. > I think the question is also interesting > because people often talk about how great > the world would be if P=NP and we could > easily solve NP problems. Actually, people mostly talk about how the world would be much better if NP != P. > However, this talk is typically only > "theoretical" (about problems and not > instances). Of course - people are researching how to solve the problems, specific instances are specific instances, whereas the research challenge is algorithms for the problem. > If someone can claim the world would > be better off with faster solutions, > they should be able to provide an > instance whose solution would lead > to a better world. Why? Often we don't know the true benefits of an advance in science or technology until well after it's done, dusted, commercialized, and in the hands of ordinary people. Given that there currently are no ways to solve big, hard instances of NPC problems, why should people bother to find specific instances?

jsprogrammer 11y ago
>Actually, people mostly talk about how the world would be much better if NP != P. I know I've seen some arguments stating as such. If you know of a well-founded one, I'd be interested in reading it. Personally, I don't know or have a strong opinion. Seems like either could be viewed as "better" in some way. >But you know someone who claims to be able to solve subset-sum problems quickly. I have a graph to 3-color, I wonder if I should convert it into a subset-sum problem for them to solve. That would take some time, and I'm pretty sure it won't be worth it. I'll have a think. Well, I actually wrote up some tests for him and he ran his algorithm against it. I also gave him a ~10MB text file containing a very large list of integers (I forget the range at the moment. I could find it if you'd like, but I'm not sure how meaningful it is.) with a randomly selected target sum. He provided the solution (which I have not verified) in ~6-9 months. He also ran through many thousands of problem instances (subset sum...in JSON arrays) with varying parameters (number of integers; range of integers) over the course over several days. I made a rudimentary plot of the parameters and timings and in my very limited analysis, it did appear that there was a sub-exponential trend (at least for the instances that he provided solutions to [:)]). I've been searching for the results (all instances, solutions, and timings) that I had collected from the test machine, but I haven't been able to find them yet. However, all of the test code is on GitHub and packaged into Docker containers for easy deployment of the test server and basic visualization of the results. I'd guess he (the person who claims a P=NP proof and sub-exponential-time subset sum solver) would be willing to run his algorithm against the test server again.
- ColinWright 11y ago
  >> Actually, people mostly talk about how >> the world would be much better if NP != P. > Seems like either could be viewed as > "better" in some way. Indeed, it depends on your internal axioms about "better". I don't have strong feelings either way either, and my feelings don't affect what's true and what isn't. The problem is open, remains open, and we deal with what's in front of us. >> But you know someone who claims to be >> able to solve subset-sum problems quickly. > ... He also ran through many thousands > of problem instances ... with varying > parameters ... it did appear that there > was a sub-exponential trend ... Unfortunately that means exactly nothing. The whole point is that for many (perhaps most) problems, the proportion of hard instances gets vanishingly small, and yet those are the ones that we often need to solve. Showing a sub-exponential trend for randomly chosen instances, or worse, instances he's chosen to show you, is no evidence at all. >> I have a graph to 3-color, I wonder if >> I should convert it into a subset-sum >> problem for them to solve. > I'd guess he (the person who claims a > P=NP proof and sub-exponential-time > subset sum solver) would be willing > to run his algorithm ... Perhaps that would be interesting. I'll look into how easy the conversion might be.