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.

PCPlus logoIn 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 * 10143 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.)

Album cover for The Collection 1977-1982Now playing:
Stranglers - Duchess
(from The Collection 1977-1982)

Loading similar posts...   Loading links to posts on similar topics...

No Responses

Feel free to add a comment...

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

  •  Emphasize with italics: surround word with underscores _emphasis_
  •  Emphasize strongly: surround word with double-asterisks **strong**
  •  Link: surround text with square brackets, url with parentheses [text](url)
  •  Inline code: surround text with backticks `IEnumerable`
  •  Unordered list: start each line with an asterisk, space * an item
  •  Ordered list: start each line with a digit, period, space 1. an item
  •  Insert code block: start each line with four spaces
  •  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...
Preview of response