7 ms·

I admit that I may be using terms in non-standard ways and that my implied definitions may not be fully consistent. I apologize for any confusion it may cause.

I admit that I may be using terms in non-standard ways and that my implied definitions may not be fully consistent. I apologize for any confusion it may cause. If you have a standard glossary of terms I could probably reformulate the statements in those terms. >I still don't understand what you mean by the word "theoretical". These are practical problems, instances of which turn up all over the world every day. Given that we want to solve these instances of these problems, in what sense are the problems "theoretical"? I probably shouldn't have used the word. It's not very good. To answer your question, though, they are theoretical in the sense that "better packing" is not an actual driven route that used less resources than the route chosen by another algorithm would have; rather, it is just a description, or template, of the result you (or someone) desire. >What do you mean by "solving", "problem", and "benefit"? These are genuine questions - you seem to be using these words in ways I don't recognise. Roughly: problem = complete data/parameters that can be fed to an NP solver (either search and verify every permutation of the solution space or (hypothetical) specialized solver) solving = the process of computing the solution to the problem and outputting the answer benefit = resources saved by applying an optimal solution instead of the sub-optimal solution that would have been used otherwise >So you don't know what a practical problem is? I was being a bit facetious, but the statement is still true, I believe (depending on what you meant by your question). I know what a practical problem is, I just do not have have an actual instance whose solution would be beneficial. My question is to be provided with such a problem. >Is that what you're calling a practical problem? Is what you're calling a "practical problem" simply a specific instance? I believe we'd call it an instance of some form of the subset sum problem (I believe it can be formulated more formally). >I can provide for you a specific instance of a three-coloring problem. Sure. But, please don't be expecting me to solve it :)

ColinWright 11y ago
> ... I may be using terms in non-standard > ways ... This is a typical difficulty. You would do really well to learn and use the words in the usual way, because then people won't get confused, and indeed, you may actually find your questions have already been answered. Problem: A collection of instances Instance: A specific question to answer Typically in early complexity theory we talk about Yes/No questions, but usually Yes/No questions can be leveraged into actual answers, so the distinction is often blurred. For example, the NP question for G3C is "Can this graph be three-colored?" - that's a Yes/No question. But there's a polynomial process for converting that into an actual coloring, if it exists. >> Given that we want to solve these >> instances of these problems, in >> what sense are the problems >> "theoretical"? > ... they are theoretical in the sense > that "better packing" is not an actual > driven route that used less resources > than the route chosen by another > algorithm would have; rather, it is > just a description, or template, of > the result you (or someone) desire. The Knapsack problem is a very real and practical problem. People have instances of it every day. Most instances are easily solved by existing algorithms, but some instances are not. The question is: Here's a knapsack, and a collection of sizes and values - can you pack things into the knapsack and get a value bigger than X? For some instances of that, real instances that turn up in the real world, the best known algorithms are exponential in performance. I would not call that "theoretical". I would call that "practical". If you call it "theoretical" then I don't understand what you mean. Are you simply saying that the general definition of the problem is "theoretical", as opposed to an actual instance? That would seem perverse. >> What do you mean by "solving", "problem", >> and "benefit"? These are genuine questions >> - you seem to be using these words in ways >> I don't recognise. > Roughly: > problem = complete data/parameters that can > be fed to an NP solver (either > search and verify every permutation > of the solution space or (hypothetical) > specialized solver) What you describe would usually be called an instance. > solving = the process of computing the solution > to the problem and outputting the answer Substituting "instance" for "problem", that's reasonable. But here you've only computed the answer to the instance. If you want to "solve" the problem, you need to produce an algorithm. That algorithm is than used to compute the answer in specific instances. > benefit = resources saved by applying an optimal > solution instead of the sub-optimal > solution that would have been used > otherwise How do you know what would have been used otherwise? This seems poorly defined. >> So you don't know what a practical problem is? > I know what a practical problem is, I just do > not have have an actual instance whose solution > would be beneficial. My question is to be provided > with such a problem. Specific instances are specific instances. Different people have different instances, and they are not universal. I don't see what you're asking for. >> Is that what you're calling a practical problem? >> Is what you're calling a "practical problem" >> simply a specific instance? > I believe we'd call it an instance of some form > of the subset sum problem (I believe it can be > formulated more formally). Yes, that's an instance. You still haven't said if that's an example of what you mean by a "practical" "problem". >> I can provide for you a specific instance of >> a three-coloring problem. > Sure. But, please don't be expecting me to solve it :) What would you do with it?
- jsprogrammer 11y ago
  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.
  - 11y ago

ColinWright 11y ago

> ... I may be using terms in non-standard > ways ... This is a typical difficulty. You would do really well to learn and use the words in the usual way, because then people won't get confused, and indeed, you may actually find your questions have already been answered. Problem: A collection of instances Instance: A specific question to answer Typically in early complexity theory we talk about Yes/No questions, but usually Yes/No questions can be leveraged into actual answers, so the distinction is often blurred. For example, the NP question for G3C is "Can this graph be three-colored?" - that's a Yes/No question. But there's a polynomial process for converting that into an actual coloring, if it exists. >> Given that we want to solve these >> instances of these problems, in >> what sense are the problems >> "theoretical"? > ... they are theoretical in the sense > that "better packing" is not an actual > driven route that used less resources > than the route chosen by another > algorithm would have; rather, it is > just a description, or template, of > the result you (or someone) desire. The Knapsack problem is a very real and practical problem. People have instances of it every day. Most instances are easily solved by existing algorithms, but some instances are not. The question is: Here's a knapsack, and a collection of sizes and values - can you pack things into the knapsack and get a value bigger than X? For some instances of that, real instances that turn up in the real world, the best known algorithms are exponential in performance. I would not call that "theoretical". I would call that "practical". If you call it "theoretical" then I don't understand what you mean. Are you simply saying that the general definition of the problem is "theoretical", as opposed to an actual instance? That would seem perverse. >> What do you mean by "solving", "problem", >> and "benefit"? These are genuine questions >> - you seem to be using these words in ways >> I don't recognise. > Roughly: > problem = complete data/parameters that can > be fed to an NP solver (either > search and verify every permutation > of the solution space or (hypothetical) > specialized solver) What you describe would usually be called an instance. > solving = the process of computing the solution > to the problem and outputting the answer Substituting "instance" for "problem", that's reasonable. But here you've only computed the answer to the instance. If you want to "solve" the problem, you need to produce an algorithm. That algorithm is than used to compute the answer in specific instances. > benefit = resources saved by applying an optimal > solution instead of the sub-optimal > solution that would have been used > otherwise How do you know what would have been used otherwise? This seems poorly defined. >> So you don't know what a practical problem is? > I know what a practical problem is, I just do > not have have an actual instance whose solution > would be beneficial. My question is to be provided > with such a problem. Specific instances are specific instances. Different people have different instances, and they are not universal. I don't see what you're asking for. >> Is that what you're calling a practical problem? >> Is what you're calling a "practical problem" >> simply a specific instance? > I believe we'd call it an instance of some form > of the subset sum problem (I believe it can be > formulated more formally). Yes, that's an instance. You still haven't said if that's an example of what you mean by a "practical" "problem". >> I can provide for you a specific instance of >> a three-coloring problem. > Sure. But, please don't be expecting me to solve it :) What would you do with it?

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