Am sure many of you are following the latest developments [Geomblog , Lipton] with interest. P vs NP is one of The Millennium Problems. Here's a neat explanation of the problem with the use of Minesweeper game.
- Log in to post comments
More like this
Now that we've gone through a very basic introduction to computational complexity, we're ready
to take a high-level glimpse at some of the more interesting things that arise from it. The one
that you'll hear about most often is "P vs NP", which is what I'm going to write about today.
So, what are…
In my last post on game theory, I said that you could find an optimal
probabilistic grand strategy for any two-player, simultaneous move, zero-sum game.
It's done through something called linear programming. But linear programming
is useful for a whole lot more than just game theory.
Linear…
Someone shoot me if I ever use the term NP-complete in a sentence. Or at least if I ever use the term in a conversation with "civilians."
Such is the dilemma of reading and reviewing a wonderful book like Lance Fortnow's The Golden Ticket: P, NP, and the Search for the Impossible. I'll be tempted…
University of Washington researchers have developed a vocal mouse that moves the cursor around the screen with clicks and phonemes:
The Internet offers wide appeal to people with disabilities. But many of those same people find it frustrating or impossible to use a handheld mouse. Software…