One topic that comes up on a regular basis is the question of how to come up with open problems that might be suitable for tackling. Of course everyone knows about P vs. NP, and like Fermat’s Last Theorem in number theory, this problem can serve as motivation for studying the foundations of computational [...]
Jim Gibbon is holding a contest to see who can best describe a piece of academic research in the form of a haiku. You’ll need to hurry though, because the deadline for submission is the 21st. (Hat tip to OmniBrain.)
My own submission is as follows:
There exist problemsintractable to decideyet easy to check
For those [...]
First off, let me just say that unlike the last couple of posts, today’s entry actually is about P vs. NP.
A blog I’ve been reading lately is Logicomp by Anthony Widjaja To, which explores the connections between logic and computational complexity. There are a couple of things about his blog I really like. [...]
Hi again,
It’s been a little longer than I would like since my last post, but we’ve been taking turns getting sick in my family and it’s slowed me down a bit. Well, this is wishful thinking but maybe it will help build up my immune system for the upcoming outbreak of avian flu.
Since this is [...]
Last night I figured out how to prove that P != NP. Well, okay, not exactly. I didn’t have a “Ureka!” moment where I suddenly understood what technique to use to show P != NP. What did occur to me was a general approach that, with a lot of time and effort, might conceivably lead [...]