Archive for the 'Bash' Category
XKCD Embedding NP-Complete Problems In Restaurant Orders
There is very popular web comic called XKCD. The site seems to have been around since January of 2006 and I’m sure that anyone that reads Digg or Reddit will be familiar with them. I visit there from time to time and even have a couple of their comics taped to my desk at work.
A few weeks ago Jordan brought up one in particular because of a job listing for a “consulting and software development firm”. The comic is a bit old and is from earlier this year in July. In the job listing they had a programming exercise referring to that comic and wanted it to work on multiple data sets read from a file. The problem in the comic is np-complete. If you aren’t familiar with that term than you might want to read up. Quoting the article on nist.gov below.
Note: A trivial example of NP, but (presumably) not NP-complete is finding the bitwise AND of two strings of N boolean bits. The problem is NP, since one can quickly (in time ?(N)) verify that the answer is correct, but knowing how to AND two bit strings doesn’t help one quickly find, say, a Hamiltonian cycle or tour of a graph. So bitwise AND is not NP-complete (as far as we know).
No comments
