How do you explain NP-Completeness/Unsolvability to a non-technical supervisor?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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?

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.