4/28/11

P, NP and Edmonds' Blossom Algorithm

I've been asked why I am one of the few people who believe that P might equal NP. To answer that, let's dive into the start of the previous century with the following question:
[MATCH] A matching in a graph is a set of edges, no two of which meet at a common vertex. A maximum matching is a matching of maximum cardinality. Is matching in P?
During the start of the previous century, almost all mathematicians believed MATCH to be in NP. It was obvious for them by the following reasoning: We -mathematicians- are smart. Since We are smart, and no polynomial algorithm has been found for MATCH, it is clearly true that MATCH is in NP. QED.


True, until mr. Edmonds came along and gave a polynomial algorithm for matching.


The fact that people believe something to be true doesn't make it true. And, generalizing that, in my opinion, therefor P=NP should be seen as an open conjecture.

The open question I've looked at, of course, is: Why, or why not, does SAT reduce to MATCH? But, that's for later.

4/18/11

3Pad

Just a prediction: After the iPad, what will -must- follow. The 3D iPad, of course, what else? Wondering how many years it will take...

4/17/11

Robots enter Fukushima reactor building