4 ms·
>> 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. T
by ColinWright 11y ago
>> 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_theory#Problem_instances https://en.wikipedia.org/wiki/Computational_complexity_theor...
- jsprogrammer 11y agoIt sounds like you know exactly what I'm asking, but are being intentionally obtuse. >and there is no way I can give you that data. Can't give because it's physically and/or logically impossible? Or, because you or your superior authority prefer not to? >Largely it's the same thing. Largely, but not precisely. A proof would need to be formulated in terms of bits. >If marketed properly, people will throw money at you to solve their instances. Sure. I think part of my question implies, "How do you market such an algorithm? At the end of the day, you need instances to feed the solver. How you get those instances into the solver?" Assume you have everyone throwing money at you. Which instances do you solve given the resources you have? Picking the largest bundle of cash headed your way doesn't seem like it would necessarily give you the 'best results' (in terms of benefit, as described previously).
- ColinWright 11y agoIf all else fails, assume good faith. If people are trying to upset you, they will be thwarted by your reaction. If people really are acting in good faith, then your reaction is correct. > It sounds like you know exactly what > I'm asking, but are being intentionally > obtuse. No, I really don't know what you're asking. It sounds like you're asking people simply to give you big, hard instances of problems that are known to be NPC. If that's what you're asking, why don't you just say so? What's the nonsense with "theoretical" and other things? If it's not what you're asking, then what are you asking? >> ... and there is no way I can give you that data. > Can't give because it's physically and/or logically > impossible? Or, because you or your superior authority > prefer not to? It's commercially sensitive data. People are paying us money to provide systems that solve problems like this. We do it better than anyone else currently does, and we get paid for it. We are contractually obliged to keep the data secure, and we are obliged by commercial concerns not to pass it on anyway. >>> 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. > Largely, but not precisely. A proof would need > to be formulated in terms of bits. If you have it in terms of bytes, multiply by eight. Scalar factors simply don't matter in this field, they really don't. If you can put the instance in a file, simply count the bytes in the file. In the end it comes to the same thing because we are talking about big-Oh-type things - worst cases and limits >> If marketed properly, people will throw >> money at you to solve their instances. > I think part of my question implies, "How > do you market such an algorithm? At the > end of the day, you need instances to feed > the solver. How you get those instances > into the solver?" So is this your problem/question: We have a program that solves instances of problem X, which is NPC. We claim it's polynomial, but need to test it. Please can someone give us instances they believe are difficult so we can prove our program is worth looking at. Is that what you're asking? Which NPC problem does the algorithm/program solve? > Assume you have everyone throwing money > at you. Which instances do you solve given > the resources you have? Picking the largest > bundle of cash headed your way doesn't seem > like it would necessarily give you the 'best > results' (in terms of benefit, as described > previously). I don't understand why you're asking about "best results" - the market will sort that for you. Get a reputation for solving instances of problems believed to be hard, and the people who will derive the best benefit will have the greatest incentive to offer you the most money. Or just solve the one that gets you the most money and buy another machine. Understand this - what you're asking, and this entire conversation - just doesn't make sense to me. Either you're not being honest, or there is a complete mis-match between our respective understandings of the whole problem area. Going back to my first paragraph I'll assume the latter. I just don't understand why you are saying what you're saying. So let me ask this. Is this your question: I claim to have solved P=NP by constructing a program/machine that solves hard instances problem X - known to be NPC. I need to test it and prove to people that it works. How do I do that? If that's your question then * I have no idea why you were ever talking about "theoretical" problems, * I have some suggestions, * I'd like to know what problem X is. If that's not your question, perhaps you should re-read this thread and simply start again with a simple, single, clear question.