6 ms·

>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 ex

>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.

ColinWright 11y ago
>> ... 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. Of course. >> 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. Technically the latter is not a problem, it's an instance. It's widely believed that for most problems, most instances are comparatively easy to solve using the "obvious" techniques. > 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. That's pretty much the belief of everyone. > 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. Well, when you have an instance to solve, you don't have a choice. If it's an easy instance then it's an easy instance. But if it's a hard instance then it's a hard instance, and it will take exponential time (using the algorithms we currently have). > 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. You keep using the word "problem" in different senses. There aren't parameters for algorithms, there are instances of problems, and we don't get to choose. >> 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." So if I give you a specific graph to three colour, is that a practical problem? I'm still struggling to understand what you mean - you keep changing the way you use words, or using them in non-standard ways. Are you just looking for a specific instance of a problem? >> better packing, better scheduling, better >> layouts for processors > What you are referring to here, I have been > referring to as "theoretical". 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"? > 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? 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. >> Can you give me any example of anything >> you would call a practical problem? > That is my question. :) So you don't know what a practical problem is? > But, a toy example would be roughly > ... > Provide a subset of > [-12,30,7,9,-84,24,1,8,3,-5,2] > that sums to 0. Is that what you're calling a practical problem? Is what you're calling a "practical problem" simply a specific instance? I can provide for you a specific instance of a three-coloring problem.

ColinWright 11y ago

>> ... 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. Of course. >> 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. Technically the latter is not a problem, it's an instance. It's widely believed that for most problems, most instances are comparatively easy to solve using the "obvious" techniques. > 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. That's pretty much the belief of everyone. > 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. Well, when you have an instance to solve, you don't have a choice. If it's an easy instance then it's an easy instance. But if it's a hard instance then it's a hard instance, and it will take exponential time (using the algorithms we currently have). > 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. You keep using the word "problem" in different senses. There aren't parameters for algorithms, there are instances of problems, and we don't get to choose. >> 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." So if I give you a specific graph to three colour, is that a practical problem? I'm still struggling to understand what you mean - you keep changing the way you use words, or using them in non-standard ways. Are you just looking for a specific instance of a problem? >> better packing, better scheduling, better >> layouts for processors > What you are referring to here, I have been > referring to as "theoretical". 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"? > 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? 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. >> Can you give me any example of anything >> you would call a practical problem? > That is my question. :) So you don't know what a practical problem is? > But, a toy example would be roughly > ... > Provide a subset of > [-12,30,7,9,-84,24,1,8,3,-5,2] > that sums to 0. Is that what you're calling a practical problem? Is what you're calling a "practical problem" simply a specific instance? I can provide for you a specific instance of a three-coloring problem.