## So What’s NP-complete Anyway?

Since there are so many good sources defining NP-complete (see below) I will just give my “elevator pitch”.

To say that a problem is NP-complete means that there is no *known* way of efficiently computing answers to the problem in general. There will always be a worst case when the computation will require exponential time to finish. However, given any proposed *solution* to an NP-complete problem, it is possible to efficiently check whether the solution is correct or not. A popular example is the Traveling Salesman Problem (TSP) which is the problem of computing the cheapest way to visit, say, all major cities in the USA for any given timetable and cost.

Moreover, a NP-complete problem can be efficiently translated into any other NP-complete problem, which implies that should one NP-complete problem have a particularly efficient solution, so will all the other problems in this class.

There are many problems that are found to be NP-complete, for instance Graph Coloring, the basis for my puzzle Chrome-8.

Here’s a short list of references:

- Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.
- Wikipedia
- Scott Aaronson. NP-complete Problems and Physical Reality

Have fun!

/M

[…] bold as to direct you to a short note I wrote some time ago, that also contains further references: So What’s NP-complete Anyway? Developer Quotidian Cheers, Reply With Quote + Reply to Thread « Previous […]