5 ms·

Maybe I can define my thoughts using some of your words. >People have instances of it every day. Most instances are easily solved by existing algorithms, but s

Maybe I can define my thoughts using some of your words. >People have instances of it every day. Most instances are easily solved by existing algorithms, but some instances are not. Ok, if you show me an instance an actual person has, I would consider it a 'practical problem', now, 'practical instance'. Given an instance, you could compute "benefit" as such: (resources_used_by_using_solution_provided_by_"existing_algorithms") - (resources_used_by_using_solution_provided_by_sub_NP_space_time_solver|presumably_optimal) Note, I'm not (directly) talking about the resources used for the computation, but rather the resources used in the real-world by taking advice from an algorithm. For instance, in the UPS example, fuel and labor costs depend on the exact route decided by UPS's logistics algorithm. Most likely that route is not 'optimal', but may be pretty close (not many resources would be saved by using the optimal route over whatever other route UPS ends up driving). >What would you do with it? I would certainly look at it and at least make a cursory attempt at solving it. However, the reason I originally asked the question was so that I could have a legitimate problem (with instances) to give to someone who claims a P=NP proof in addition to an algorithm. He can solve most random subset sum problems, of the kind I gave you, with decently sized sets (thousands of elements) and randomly selected targets very quickly. However, I think that random subset sum problems might be pretty easy. 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. But, assuming P=NP and we have a runnable algorithm (which I don't necessary believe, but do allow for), I am interested in finding and solving the problems that would have the largest benefit (as previously defined). Assume you can only solve a single instance at a time, what order do you solve them in? Edit about terminology: Like I said, if you have a standard glossary I could probably wield it effectively in our conversation. However, I typically find that there are few globally standard terms. Instead, each sub-culture seems to define their own very technical definitions of words. Sometimes these are similar to other culture's definitions, sometimes not. Selecting which sub-cultures to borrow from is tricky and there is certainly no right answer, but I also see that there is tremendous value in having similar definitions. If you do have a good reference, I'd appreciate it.

ColinWright 11y ago
>> People have instances of it every day. > Ok, if you show me an instance an actual > person has, ... School timetabling can be cast as a SAT problem. That's a real problem that real people have. > I would consider it a 'practical problem', > now, 'practical instance'. There seems to be a real mismatch here. I'm not going to be able to get someone else's commercially sensitive specific instance and give that to you. I'm not sure what you think you're asking. Your "clarifications" just make me more confused. Let me try to state this clearly: * People have real instances of problems that are known to be NP-Complete. * Some of those instances are hard to solve. * There is no way that people will give to you, a random person, their commercially sensitive instances. Let me be even clearer: * In one of my companies we run SAT solvers to try to find solutions to instances of known NP-Complete problems, and there is no way I can give you that data. So, what are you asking for? > I'm ... talking about ... the resources > used in the real-world by taking advice > from an algorithm. ?? > For instance, in the UPS example, fuel > and labor costs depend on the exact route > decided by UPS's logistics algorithm. Most > likely that route is not 'optimal', but > may be pretty close (not many resources > would be saved by using the optimal route > over whatever other route UPS ends up > driving). Even for instances that are hard there are approximation algorithms that get approximate solutions. Of course they're close, but sometimes they're not very close. This is an active area of research. >> What would you do with it? > I would certainly look at it and at least > make a cursory attempt at solving it. Hmm. > However, the reason I originally asked > the question was so that I could have a > legitimate problem (with instances) to > give to someone who claims a P=NP proof > in addition to an algorithm. Well, there's the problem. The web is littered with people claiming algorithms for P=NP. What problem do they claim to have an algorithm for? If I provide a G3C instance, will they be able to use their algorithm on it? > He can solve most random subset sum problems, > of the kind I gave you, with decently sized > sets (thousands of elements) and randomly > selected targets very quickly. However, > I think that random subset sum problems > might be pretty easy. Exactly. > 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. > But, assuming P=NP and we have a runnable > algorithm ... I am interested in finding > and solving the problems that would have > the largest benefit ... If you, or he, genuinely do have a program to solve hard instances of an NPC problem, you'll have no problem getting real instances. If marketed properly, people will throw money at you to solve their instances. > Assume you can only solve a single instance > at a time, what order do you solve them in? ?? You have an instance, you solve it. I don't understand your question. Look, it's not NPC, but think about factoring integers. People really do want to factor big numbers. Each number is an instance, and there are a gazillion of them that people want factored. Which one do you do? The one people offer the most money for. > ... if you have a standard glossary I could > probably wield it effectively in our conversation. We've mostly covered the terms that matter. The difficulty isn't with the technical terms, the problem is that I can't find a sensible question that you might be asking. > If you do have a good reference, I'd appreciate it. This is actually quite reasonable: https://en.wikipedia.org/wiki/Computational_complexity_theory#Problem_instances https://en.wikipedia.org/wiki/Computational_complexity_theor...

ColinWright 11y ago

>> People have instances of it every day. > Ok, if you show me an instance an actual > person has, ... School timetabling can be cast as a SAT problem. That's a real problem that real people have. > I would consider it a 'practical problem', > now, 'practical instance'. There seems to be a real mismatch here. I'm not going to be able to get someone else's commercially sensitive specific instance and give that to you. I'm not sure what you think you're asking. Your "clarifications" just make me more confused. Let me try to state this clearly: * People have real instances of problems that are known to be NP-Complete. * Some of those instances are hard to solve. * There is no way that people will give to you, a random person, their commercially sensitive instances. Let me be even clearer: * In one of my companies we run SAT solvers to try to find solutions to instances of known NP-Complete problems, and there is no way I can give you that data. So, what are you asking for? > I'm ... talking about ... the resources > used in the real-world by taking advice > from an algorithm. ?? > For instance, in the UPS example, fuel > and labor costs depend on the exact route > decided by UPS's logistics algorithm. Most > likely that route is not 'optimal', but > may be pretty close (not many resources > would be saved by using the optimal route > over whatever other route UPS ends up > driving). Even for instances that are hard there are approximation algorithms that get approximate solutions. Of course they're close, but sometimes they're not very close. This is an active area of research. >> What would you do with it? > I would certainly look at it and at least > make a cursory attempt at solving it. Hmm. > However, the reason I originally asked > the question was so that I could have a > legitimate problem (with instances) to > give to someone who claims a P=NP proof > in addition to an algorithm. Well, there's the problem. The web is littered with people claiming algorithms for P=NP. What problem do they claim to have an algorithm for? If I provide a G3C instance, will they be able to use their algorithm on it? > He can solve most random subset sum problems, > of the kind I gave you, with decently sized > sets (thousands of elements) and randomly > selected targets very quickly. However, > I think that random subset sum problems > might be pretty easy. Exactly. > 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. > But, assuming P=NP and we have a runnable > algorithm ... I am interested in finding > and solving the problems that would have > the largest benefit ... If you, or he, genuinely do have a program to solve hard instances of an NPC problem, you'll have no problem getting real instances. If marketed properly, people will throw money at you to solve their instances. > Assume you can only solve a single instance > at a time, what order do you solve them in? ?? You have an instance, you solve it. I don't understand your question. Look, it's not NPC, but think about factoring integers. People really do want to factor big numbers. Each number is an instance, and there are a gazillion of them that people want factored. Which one do you do? The one people offer the most money for. > ... if you have a standard glossary I could > probably wield it effectively in our conversation. We've mostly covered the terms that matter. The difficulty isn't with the technical terms, the problem is that I can't find a sensible question that you might be asking. > If you do have a good reference, I'd appreciate it. This is actually quite reasonable: https://en.wikipedia.org/wiki/Computational_complexity_theory#Problem_instances https://en.wikipedia.org/wiki/Computational_complexity_theor...