does not being aware of np-completeness make you dumb?

I have recently been reading a series of posts ([1][2][3]) from authors about the pros and cons of having or not having a degree in CS. I’m sure the argument goes both ways, but my thoughts are focused on how does someone who has not spent 4 years obtaining a degree, accrue the knowledge they may need.

For the purpose of this post I will use the concept of NP-completeness (or in fact algorithmics in general) as an example. I think from experience I have learned that NP-completeness is a topic that quite a few developers are not familiar with despite its importance in the field. Many may be aware of it through Jeff Atwood‘s post over at codinghorror, where he suffered at the hands of the topic’s rigour.

So how does someone who has never obtained a CS degree find out about such a topic? My feeling is that they don’t. OK some people will go out their way to find such topics but I haven’t met too many that do. Some may even point out that NP-completeness did (does) not appear on their course curriculum, in which case it probably boils down to Dan Dyer‘s point about the virtues of choosing a good university course. What I’m trying to say is that someone who goes to a decent university and obtains a good degree has spent (possibly) 4 years learning about the foundations of computing, giving them a good base to make important technical decisions.

For example. You are hit with a problem at work, let’s say some sort of job scheduling problem or even allocation of people to resources. The problem seems easy when described and the agile developer takes over you and you start churning out code. However, if this person had only taken a simple algorithms course at university, he might have thought twice about jumping into such a problem – as many variants of such problems are known to be NP-hard.

This brings me back round to my question, where do such developers learn about these things? They may read articles on sites like dZone or reddit, but c’mon, let’s face it, these sites are pretty good at giving you the latest articles about Java, .NET, jQuery, but it’s rare that you see an article about algorithmic issues rise to the top of the popularity list. I mean who wants to read the details of what a B+ Tree, Trie, Boyer-Moore string matching algorithm, etc are, because it’s hard going, instead most will take the easy option of reading guff like 7 ways to write beautiful code. However, if you attend university you are forced to know many of the finer details of CS, as you are examined on them. OK, you may not need them for a simple web app, but an employer is certainly going to be happier that you have the details in your head should you need them. The point is that you never know when you are going to need such things, and knowing when you do is maybe what you spend 4 years gaining.

practically np

Often I find that people have the opinion that the class of NP-complete problems, as discussed in my previous post, in general, don’t show up in practice. And if they do show up, then they normally represent a restriction on the problem that we can solve easily. This line of thought though is unfortunately untrue 🙁 .

An example of a problem that has significant practical consequences, yet is NP-hard, is that of finding a maximum size stable matching in the context of what is known as the Hospital/Residents problem with ties.

In the Hospital/Residents problem (HR), we seek to assign a set of student doctors (residents) to hospital posts (a hospital may offer more than one post) – this task is carried out in many countries in a student’s first year after graduating from medical school. Each student is asked to rank a set of hospitals in strict preference order, with the hospitals ranking the set of students also by preference. However, in many schemes, hospital’s preference lists are allowed to contain ties. That is, a hospital is allowed to be indifferent between a set of students – this generally produces a more realistic set of preference lists, as otherwise the hospital may typically have to rank several thousand students individually. We note that this description of the problem is not complete but I’m describing a known practical situation here, not the general case of HR with ties, where a student’s preference list may also contain ties.

So what is a stable matching? A matching is stable in the context above if there is no student s that strictly prefers a hospital h to his current assignee h' (or s is unmatched), and h is either under-subscribed or prefers s to at least one assignee. I think an example will better illustrate:

students       hospitals
s: h h'         h: s (t r)
t: h h'         h': r s t
r: h h'

The above states that student s prefers h to h', similarly for students t and r. For the hospitals, each is offering 1 post, and hospital h is indifferent between t and r and prefers s to both of them, with h' preferring r to s to t respectively. Now the matching {(t,h),(r,h')} is not stable. Why? Because s is unmatched and would rather be assigned to h than be unmatched, and h prefers s to t, so both s and h would get better off if h reject t and took on s. In this example a stable matching is {(s,h),(r,h')}.

Mmmmm maybe the last bit was a little complicated but I just wanted to give a feel for why we desire a matching to be stable.

As I mentioned earlier the problem of finding a maximum stable matching in this context is NP-hard. So why is this a problem? Well obviously we want to match as many students as possible, if not these people will not get a job, so this is very important to them. Also, clearly we want a matching to be stable for otherwise you end up with chaos as students and hospitals realise that they would be better off if they just switched. This is exactly what happened in the US prior to establishing a system (NRMP) that was based on stable matchings way back in the 50s.

However, despite its importance as a problem we are stuck! If we want to deal with ties (and also if we have no ties but “couples” who want to submit joint preference lists) we are in the realms of using heuristics. What this means is that we are highly unlikely to find a solution that maximises the number of students matched. This may not sound bad to you, but to those involved in the matching scheme, it could affect the rest of their life. That said, even a stable solution less than optimal size (it’s easy to find such a solution in polynomial-time) is more acceptable than a solution that is not stable.

Anyway, there you have it, a practical NP-hard problem. Also, there are many others. If this was of interest then I can maybe write up something about the Kidney Exchange Problem – this concerns the organisation of kidney transplants from live donors and it is known that the most important practical variants of this problem are NP-hard. This is in every sense of the word a life or death problem.

NP-completemess

Well yesterday I read a blog post by Jeff Atwood over at www.codinghorror.com about NP-completeness. In the comments to his post I felt that Jeff got a somewhat raw deal with the criticism he received. Ok, the details of his post were not exactly accurate to the nth degree, but his post may have identified a problem set that some of his many readers may never otherwise have been aware of. This has got to be a good thing, right?

So anyway, with a little experience on my side with these NP-complete problems maybe I will try to shed some further light on the details. Remember though, this is quite a complicated area and many books have been written about this stuff and many will save a whole chapter just as an introduction. Thus, I will try to keep this as light as possible and hopefully the detractors can fill in their own details where I leave them out.

First, one of the biggest questions in the field of computer science is does P=NP. For those that wish to pursue research in this area, there is the Millenium Prize Fund offering a cool $1million for a proof either way of this question. Those living in the UK will be hoping that it’s paid in dollars with the piss poor exchange rate 😉 .

Now what is P? Well P is the set of problems that can be solved in polynomial time. That is, a problem where an algorithm is known to take O(n^k), where n is the size of the input and k is some fixed constant; fixed meaning it doesn’t vary with the input size. An example of such an algorithm is Quicksort, whose complexity is O(n²).

So what is NP? Well first, NP does NOT stand for Non-Polynomial, if you want to take anything for this just take that, as it will save you embarrassment when you say it is (sorry I’ve seen this so many times). It actually stands for Non-deterministic Polynomial. Now when is a problem in NP?

For a problem to be in NP, the problem must be a decision problem. See, this is where it escalates trying to describe this stuff, as you now have to define a decision problem for all this to make sense. Anyway, a decision problem is a problem where the answer can be given as a simple ‘Yes’ or ‘No’. For example, given two cities is there a direct plane route between these cities. Clearly the answer is Yes or No. For a more computing/maths related example we can say that given a graph G, does there exist a path between two vertices, say u and v, in G.

Now that we know what a decision problem is, we can now describe what the class of problems in NP look like. Mmmmm, if only. In actual fact, I now need to describe what a non-deterministic algorithm is. Sigh. Let’s keep it simple if not 100% accurate. A non-deterministic algorithm has two phases. The first phase guesses an answer (certificate) to our problem and the second phase verifies that this certificate satisfies the constraints of the problem in polynomial-time. For example, consider the problem of matching 3 sets of people (known as 3D matching). Let’s name these people men, women and dogs, with each set having size n. So what we want is a set of (man, woman, dog) triples, such that each man, woman and dog appear in exactly one triple and the matching is of size n, i.e. everyone is matched. So the decision problem here is: given such an instance does there exist a matching of size n? The non-deterministic algorithm is: guess a set of (man,woman,dog) triples, then first verify that our set of triples is of size n, by counting the triples, and then to ensure that it is a matching, we can check that no two triples have someone in common.

Phhhhewww, that was longer than I imagined, see why Jeff’s abbreviated version may be better if not so accurate. I mean I have not even described what an NP-complete problem is yet. We can however describe what the class of problems in NP now are.

The class NP is defined as the collection of all decision problems that are polynomial-time solvable using a non-deterministic algorithm. We note here that many of the problems we see in everyday (programming) life are defined as optimization problems rather than decision problems – an optimization problem is one where we seek to maximise or minimise some property, for example the Travelling Salesman Problem. However, it is known that all optimization problems can be re-written as a decision version of the same problem.

So can we now define what an NP-complete problem is? Mmmm just about. In fact, I will state it here and then describe the one further bit of information we need. A problem X is NP-complete problem if:

X is in NP;
X is NP-hard.

Often you hear people getting confused by NP-complete and NP-hard. They are different things, an NP-hard problem need not be NP-complete, basically NP-hard problems are at least as hard as those problems in NP. Also, if a combinatorial decision problem is NP-complete we say that the optimisation problem is NP-hard.

So what does it mean for a problem to be NP-hard? Well to show that a problem is NP-hard we must show that it is polynomial-time reducible to an NP-complete problem (in fact, to be precise, what we have to show is that it is reducible to ALL NP-complete problems, however due to the transitivity of reductions we need only show it’s reducible to a single NP-complete problem). That is, we need to show that we can reduce an instance of one problem to the instance of another problem, i.e a Yes answer in one problem maps to a Yes answer in the other and vice-versa, similarly with the No answers.

Now if only we had one problem that we know is NP-complete. Well we do! This was shown in Cook’s Theorem. So now all (and I say all very lightly) we have to do to show that our problem is polynomial-time reducible to satisfiability, or some other NP-complete problem – satisfiability (SAT) is the problem Cook showed to be NP-complete. Another (classic) example of an NP-complete problem is the 3D matching problem example given above.

And there you have it, NP-completeness in just over 1000 words, although I missed a few details out I hope this is useful to someone. Incidentally I have meet Stephen Cook (ala Cooks’ theorem) before and I’m pretty sure from experience he would struggle to tell you this in under 1000 words 😉 Actually maybe not………………..

Over and out.