[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.
