>> ... 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.
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 :)
> ... 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?