in Algorithms, Complexity, Observations

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.

Write a Comment



  1. I’m not sure that it matters whether you know about NP-completeness explicitly. But I think it is important to have a feel for whether a particular solution to a problem will be feasible for a large example.

    I work in compilers, and therefore come up against a lot of problems (register allocation, scheduling, etc.) which are NP-hard. However, I don’t think that knowing these problems are NP-hard helps: it becomes obvious that the only way to completely solve some problems is \try every combination\, and that there will be too many combinations to try.

    Faced with this scenario, a smart programmer will work out clever short-cuts and approximations to find a reasonable solution quickly. I don’t think they need to know any formal details of the complexity of the problem.

    While I don’t think knowing about NP-completeness matters too much, I do frequently think about whether operations are constant-time, linear time, etc. when programming.