PCPlus 299: Answering difficult questions

I’d just read a book called Introduction to the Theory of Computation by Michael Sipser and found it fascinating enough that I tried to encapsulate what NP-complete means in a 2000-word essay for October 2010’s issue. Was I successful? You’ll have to read it to find out.

In essence, I talk a bit about big-Oh and show that algorithms that have exponential or factorial big-Oh expressions are terrible to implement since they rapidly get to the point where it just takes too long to do anything. I then elide a smidge of “intractability” and a whiff of “decidability” and introduce NP-completeness. I show that if you solve one NP-complete problem in “polynomial time”, you’ve solved all of them since they are all transformable into the “Boolean satisfiability problem” in polynomial time. So, solve that last one in polynomial time and the computing world will beat a path to your door and fête you forevermore.

(Annoying things: again I tried to have superscripts in the text. I should have learned my lesson by now: it gets lost during the typesetting. So, for example, PermSort – see the article for what it is – would take 3 * 10¹⁴³ years to sort 100 items at a rate of a million permutations per second.)

This article first appeared in issue 299, October 2010.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

  Loading links to posts on similar topics...