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