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