10 ms·

It sounds like you know exactly what I'm asking, but are being intentionally obtuse. >and there is no way I can give you that data. Can't give because it's ph

It sounds like you know exactly what I'm asking, but are being intentionally obtuse. >and there is no way I can give you that data. Can't give because it's physically and/or logically impossible? Or, because you or your superior authority prefer not to? >Largely it's the same thing. Largely, but not precisely. A proof would need to be formulated in terms of bits. >If marketed properly, people will throw money at you to solve their instances. Sure. I think part of my question implies, "How do you market such an algorithm? At the end of the day, you need instances to feed the solver. How you get those instances into the solver?" Assume you have everyone throwing money at you. Which instances do you solve given the resources you have? Picking the largest bundle of cash headed your way doesn't seem like it would necessarily give you the 'best results' (in terms of benefit, as described previously).

ColinWright 11y ago
If all else fails, assume good faith. If people are trying to upset you, they will be thwarted by your reaction. If people really are acting in good faith, then your reaction is correct. > It sounds like you know exactly what > I'm asking, but are being intentionally > obtuse. No, I really don't know what you're asking. It sounds like you're asking people simply to give you big, hard instances of problems that are known to be NPC. If that's what you're asking, why don't you just say so? What's the nonsense with "theoretical" and other things? If it's not what you're asking, then what are you asking? >> ... and there is no way I can give you that data. > Can't give because it's physically and/or logically > impossible? Or, because you or your superior authority > prefer not to? It's commercially sensitive data. People are paying us money to provide systems that solve problems like this. We do it better than anyone else currently does, and we get paid for it. We are contractually obliged to keep the data secure, and we are obliged by commercial concerns not to pass it on anyway. >>> Further, I'm not sure of the precise way >>> to measure the complexity of the algorithm >>> when just given a list of integers in ASCII. >>> I assume you really need to analyze things >>> at the bit level, instead of just the number >>> of ASCII characters. >> Largely it's the same thing. > Largely, but not precisely. A proof would need > to be formulated in terms of bits. If you have it in terms of bytes, multiply by eight. Scalar factors simply don't matter in this field, they really don't. If you can put the instance in a file, simply count the bytes in the file. In the end it comes to the same thing because we are talking about big-Oh-type things - worst cases and limits >> If marketed properly, people will throw >> money at you to solve their instances. > I think part of my question implies, "How > do you market such an algorithm? At the > end of the day, you need instances to feed > the solver. How you get those instances > into the solver?" So is this your problem/question: We have a program that solves instances of problem X, which is NPC. We claim it's polynomial, but need to test it. Please can someone give us instances they believe are difficult so we can prove our program is worth looking at. Is that what you're asking? Which NPC problem does the algorithm/program solve? > Assume you have everyone throwing money > at you. Which instances do you solve given > the resources you have? Picking the largest > bundle of cash headed your way doesn't seem > like it would necessarily give you the 'best > results' (in terms of benefit, as described > previously). I don't understand why you're asking about "best results" - the market will sort that for you. Get a reputation for solving instances of problems believed to be hard, and the people who will derive the best benefit will have the greatest incentive to offer you the most money. Or just solve the one that gets you the most money and buy another machine. Understand this - what you're asking, and this entire conversation - just doesn't make sense to me. Either you're not being honest, or there is a complete mis-match between our respective understandings of the whole problem area. Going back to my first paragraph I'll assume the latter. I just don't understand why you are saying what you're saying. So let me ask this. Is this your question: I claim to have solved P=NP by constructing a program/machine that solves hard instances problem X - known to be NPC. I need to test it and prove to people that it works. How do I do that? If that's your question then * I have no idea why you were ever talking about "theoretical" problems, * I have some suggestions, * I'd like to know what problem X is. If that's not your question, perhaps you should re-read this thread and simply start again with a simple, single, clear question.
- jsprogrammer 11y ago
  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?

ColinWright 11y ago

If all else fails, assume good faith. If people are trying to upset you, they will be thwarted by your reaction. If people really are acting in good faith, then your reaction is correct. > It sounds like you know exactly what > I'm asking, but are being intentionally > obtuse. No, I really don't know what you're asking. It sounds like you're asking people simply to give you big, hard instances of problems that are known to be NPC. If that's what you're asking, why don't you just say so? What's the nonsense with "theoretical" and other things? If it's not what you're asking, then what are you asking? >> ... and there is no way I can give you that data. > Can't give because it's physically and/or logically > impossible? Or, because you or your superior authority > prefer not to? It's commercially sensitive data. People are paying us money to provide systems that solve problems like this. We do it better than anyone else currently does, and we get paid for it. We are contractually obliged to keep the data secure, and we are obliged by commercial concerns not to pass it on anyway. >>> Further, I'm not sure of the precise way >>> to measure the complexity of the algorithm >>> when just given a list of integers in ASCII. >>> I assume you really need to analyze things >>> at the bit level, instead of just the number >>> of ASCII characters. >> Largely it's the same thing. > Largely, but not precisely. A proof would need > to be formulated in terms of bits. If you have it in terms of bytes, multiply by eight. Scalar factors simply don't matter in this field, they really don't. If you can put the instance in a file, simply count the bytes in the file. In the end it comes to the same thing because we are talking about big-Oh-type things - worst cases and limits >> If marketed properly, people will throw >> money at you to solve their instances. > I think part of my question implies, "How > do you market such an algorithm? At the > end of the day, you need instances to feed > the solver. How you get those instances > into the solver?" So is this your problem/question: We have a program that solves instances of problem X, which is NPC. We claim it's polynomial, but need to test it. Please can someone give us instances they believe are difficult so we can prove our program is worth looking at. Is that what you're asking? Which NPC problem does the algorithm/program solve? > Assume you have everyone throwing money > at you. Which instances do you solve given > the resources you have? Picking the largest > bundle of cash headed your way doesn't seem > like it would necessarily give you the 'best > results' (in terms of benefit, as described > previously). I don't understand why you're asking about "best results" - the market will sort that for you. Get a reputation for solving instances of problems believed to be hard, and the people who will derive the best benefit will have the greatest incentive to offer you the most money. Or just solve the one that gets you the most money and buy another machine. Understand this - what you're asking, and this entire conversation - just doesn't make sense to me. Either you're not being honest, or there is a complete mis-match between our respective understandings of the whole problem area. Going back to my first paragraph I'll assume the latter. I just don't understand why you are saying what you're saying. So let me ask this. Is this your question: I claim to have solved P=NP by constructing a program/machine that solves hard instances problem X - known to be NPC. I need to test it and prove to people that it works. How do I do that? If that's your question then * I have no idea why you were ever talking about "theoretical" problems, * I have some suggestions, * I'd like to know what problem X is. If that's not your question, perhaps you should re-read this thread and simply start again with a simple, single, clear question.

jsprogrammer 11y ago
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?