Iterations of NP-Complete
Thu, 20 Sep 2007
Today, NP-Complete twice popped into my attention-space. How strange that my near-random clicks would lead me to think on problems in non-deterministic polynomial time.
First, I noticed it in an article that detailed the difficulties encountered in creating a semantic web, i.e. the web in a form that computers could understand. Semantic Web: Difficulties with the Classic Approach
Later, I checked out xkcd - A webcomic of romance, sarcasm, math, and language - By Randall Munroe. There it was again!
It seems as if NP-Complete problems are becoming part of the nerd pop-culture. The P=NP problem has already attained celebrity status:
Shtetl-Optimized - What Google Won’t Find
Yeah, this is a problem so profound that it’s appeared on at least two TV shows (The Simpsons and NUMB3RS). It’s also one of the seven (now six) problems for which the Clay Math Institute is offerring a million-dollar prize for a solution.
» Comments are closed.
» Link: / ephemera / Iterations of NP-Complete