Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

You fix problems. You can do the impossible.

Co-workers come to you with a wide range of questions and problems they want you to solve; which can usually be done with some simple custom program or script. Most things are fairly simple, and they are amazed at how you can take ten minutes of your time to write a little script that saves them hundreds of hours of work in a given year.

People come to you with a problem and, having seen your past work, expect that you'll be able to take care of even the impossible in short order. But every now and again, the problem they want you to solve is one of those ones that give programmers a headache - they're NP-Complete or otherwise computationally unsolvable.

It could be an automated scheduling program, warehouse packing sorter, a system that predicts the company's stock price three years in advance, what have you.

If you tell them it's impossible, it sounds like you're just trying to get out of doing the work, or they think that impossible means impossible (as in "kind of hard, but I could do it in a few hours"). Likewise, you can't just point them to the CS theory section of your bookcase and tell them to read up on it.

How do you explain to a non-technical co-worker (or supervisor) that some task they want you to complete is literally impossible not merely the same-old impossible that you successfully deal with every day?

[Note: Offering a compromise (i.e. offering a near-optimal, not perfectly optimal, solution) or giving them what they really need, not what they think they want, is generally what I end up doing; but my question is about explaining why what they are precisely asking for isn't feasible without resorting to using highly technical terms, hand-waving, or "losing" that help ticket.]

share|improve this question
3  
MANY NP-Complete problems have very good approximate solutions. Please give specific examples of what you have been asked to do. –  Job Jun 4 '11 at 2:17
    
+1 Job. the examples given in the question may be difficult but they are not impossible. –  james Jun 6 '11 at 23:47
add comment

8 Answers

up vote 16 down vote accepted

What I did once.

Ask for some suggested algorithm. (In my case, they had some knapsack kind of problem they wanted to solve badly.)

Take a few days to work up the O complexity of the algorithm. In many cases, it's trivial because their suggestion is O(n^3) or something. This can be a little hard to explain, but it's not tough. Examples help. Write data records on paper cards and make them go through the steps of the algorithm on a small data set.

Get real sizes of the data set. Exact. Folks like to see exact. "32,767 rows of data as of Tuesday at 3:07 PM." You're not fudging.

Get a rough order of performance. For example, 5,000 rows per second can be processed by a simple SELECT on your normal production server. Round up; these numbers are approximations and vary a bit. You can be optimistic here.

Do the math.

Show them that each transaction will take 50 hours, and they want to do 100 per day.

It's great for NP algorithms because the times are so astronomically big that you can get into the "pi seconds is a nano-century" conversations.

There's not an easy way around this. In intro-to-CS classes, the professors all cover a real-world example to drive home the enormity of it. You have to do the same.

share|improve this answer
1  
It isn't their job to come up with the algorithm; it's yours. How do you stop them from expecting you to come up with a better algorithm? –  David Thornley Jun 3 '11 at 20:59
5  
@David Thornley: Since it's an NP problem, all algorithms are bad. The important part is to start with some algorithm to create an ongoing conversation focused on the insane cost of trying to implement some weird NP algorithm. You'd be surprised how many people will say "and then you simply do [X]" where [X] is some magical thing they can't really describe. That's the important part of the conversation. Focusing on the magical and undoable steps. Education like this is not a one-time presentation. –  S.Lott Jun 3 '11 at 21:05
1  
but as @David pointed out, it doesn't stop them from just going "well, why can't you come up with a more efficient algorithm then? What am I paying you for?" –  jalf Jun 3 '11 at 23:55
    
@jalf: Nothing stops them from doing that. Nothing. Since you can't stop it, you have to deal with it. Ask them for hints and suggestions and show how their ideas cannot work. Eventually, they get the idea that there are no secret better ideas. But, it's a slow process to show that the problem is hard. –  S.Lott Jun 6 '11 at 10:04
1  
@S.Lott good advice "focusing on the magic". In my experience when someone wants to do the impossible/computationally unreasonable, computability/complexity aren't the real problems, the real problem is the vagueness of the goal. Sometimes making the goal better defined makes the computational problems go away too. –  Owen Aug 26 '11 at 1:16
add comment

One problem is that it takes a good founding in automata theory to grasp the "complete" part of NP-complete. You can explain what NP is nontechnically, but not the completeness. Another problem is that we don't actually know that there isn't an efficient polynomial solution to an NP-complete problem (and, by extension, all problems in NP). We do know that some very intelligent people who have worked very hard have failed to come up with one.

Start with talking about how long it would be to try every possible combination, as some other people have suggested. Then you need to convince them that there isn't a better way to do it. This is the point where you need to bring in authority.

Tell them that this is one of the Clay Institute's millennium problems, considered one of the most important mathematical problems around. Tell them that, if you or anybody else had a good way to solve the problem efficiently, they could publish it and get a million dollar prize.

share|improve this answer
1  
+1 for the comment on the millennium problem. –  Peter Taylor Jun 3 '11 at 23:53
    
"If I knew how to solve that problem, I wouldn't be working here!" –  kba Jun 6 '11 at 21:00
add comment

It doesn't help to go all theoretical on them.

As S.Lott said, just walk them through the algorithm, as if they were doing it by hand. Anybody can understand that.

share|improve this answer
add comment

NP-complete does not mean the problem is unsolvable, just that you cannot find the best solution without trying each and every possibility. No fast solutions!

The NP-ness comes from that you can VERIFY a solution in polynomial time. For instance, for Travelling Salesman you can just add up the distances travelled in the given solution and be done. (And if you could magically guess the next journey to take thereby choosing the optimal solution as the first, you would prove that P=NP).

Note that if you can pose additional restrictions (like going A-C-B is more expensive than going A-B directly for the salesman) you can get approximation algorithms guaranteed to be within X% of the optimal solution which may be good enough. Also if you can keep the datasets small, you may keep the total running time low enough for it to be feasible even if you need to do them all.

Perhaps you were thinking of another term for uncomputable?

share|improve this answer
add comment

hmmmm. I'd start with more understandable fundamental limits. Like, there's nothing colder then absolute zero, nothing faster then the speed of light. A gallon jug can't hold 2 gallons of water (at 1 atmosphere). A shoestring can't lift car.

There's the same sort of limits on algorithms/computers/software. Some things are just too complex to be solved in reasonable time. And this isn't a matter of scale or size like counting all the sand grains in a desert. This is the sort of thing that's fundamentally beyond our limits. It's like a one-legged man in an asskicking contest.

So what I'm saying is that I'd use analogies.

share|improve this answer
    
It is harder than that to be impossible. Negative temperatures are well-defined and achievable in the laboratory. Most of the visible universe is currently receding faster than the speed of light. A gallon jug can hold 2 gallons of water if the temperature is cold enough. A shoestring can lift a car in a low g situation. (Alternately make the car a matchbox car. Or build the shoe-string out of a sufficiently strong material.) –  btilly Jun 3 '11 at 23:20
    
@btilly: If you'd given those as answers on a freshman chemistry exam, you would have just gotten a 50% score. It's not possible to achieve negative absolute temperatures because you can't have less than no molecular motion. Liquid water is not sufficiently compressible to allow two gallons of liquid water in a one-gallon jug. There are no circumstances in our universe under which either of those are feasible - not even, say, at the core of Jupiter, where hydrogen is a metal. –  Bob Murphy Jun 3 '11 at 23:47
    
@Bob Murphy: The freshman chemistry exam is wrong, see en.wikipedia.org/wiki/Negative_temperature for details. As for the "hold" question, I gave a trick answer. If the water is frozen, 2 gallons of it can be indeed held in place by a gallon jug. The water won't all fit in the jug, but it will be held. –  btilly Jun 3 '11 at 23:59
    
@btilly: There is nothing colder then absolute zero and nothing is faster then the speed of light. Read your own link. Then read this one link. But you did get me on the shoestring in zero G. And half credit for the smartypants "hold" answer. –  Philip Jun 6 '11 at 17:03
    
@btilly: All of the visible universe is receding at slower than the speed of light, almost by definition, and "currently" by itself really doesn't mean anything given the distances involved. –  David Thornley Jun 6 '11 at 18:07
show 3 more comments

The time I hit this I finally got through to them by getting them to investigate what the required hardware would cost.

It would have needed in the high 9's of disk space back when you simply didn't put that in a PC-type machine.

share|improve this answer
1  
+1 the numbers they will understand have dollar signs in front of it. build a spec, run the numbers and benchmarks, get a quote on the hardware. You might surprise them (or you might surprise yourself) –  james Jun 6 '11 at 23:44
add comment

I keep a little book in my desk called Computers Ltd: what they really cant do. Recommend that they read it. Let them borrow it. NP complete is gonna go sailing over their heads like a comet in another galaxy.

Or read it yourself and quote something from it. There are many details that us programmers consider "obvious details" that really need to be laid out for laymen.

share|improve this answer
add comment

NP-complete just means it cannot be solved in polynomial time. You can still have some code to solve it for some small numbers. For example, knapsack problem is NP-complete, but that doesn't prevent programmers to code solutions for the problem because there is a relatively efficient solution using dynamic programming (it's efficient but still not polynomial).

Also, most text books about NP-complete problems usually discuss about approximation methods to solve NP-complete problems. For example, Traveling Salesman Problem can be solved in polynomial time if you relax the requirements (the solution is at most 1.5 the best solution and the distance is metric). You can present those alternatives.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.