Should be reading more and writing less, but well...

Thursday, May 03, 2007


Counter Example

Finding counter examples to conjectures can be notoriously hard (pun? I think not). This is an area of creativity that mostly goes unappreciated.

Here's a personal anecdote: my father once came up with an algorithm to solve a hugely constrained version of the traveling salesman problem. The greedy proof was slightly hand-wavy, and I felt it would be an easier thing to find a counter example where his algorithm wouldn't find the optimal tour. Of course, I was just trying to tell him that he couldn't have solved TSP (or even approximated it). I learnt two lessons that day.

Lesson One: One must always speak sweet, because one underestimates the number of times one has to eat his own words.

Lesson Two: Finding counter examples can get quite tricky - and if I may, I would admit that it's not just tricky, it's quite hard - requires tons of patience, and a deep understanding of the problem and the algorithm we are out to disprove. I had learnt a similar lesson earlier in Sundar's Approximation Algorithms class. Sundar let us spend one hour counter-exampling that a minimum spanning tree over the vertex set wouldn't give us a minimum Steiner tree. The counter example used a 'construct' that was quite simple, and took a few minutes of dedicated thought to find. But what amazed me today was this fact about Tait's conjecture:
Tait's conjecture states that "Every polyhedron has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed in 1886 by P. G. Tait and disproved in 1946, when W. T. Tutte constructed a counterexample with 25 faces, 69 edges and 46 vertices.
Imagine the patience, creativity, deep understanding of the problem, and the [least appreciated of them all] ability to borrow from related problems and areas - it takes to come up with such a counter example. And I keep wondering: why research?

Labels: ,


February 2004   July 2004   August 2004   September 2004   October 2004   November 2004   December 2004   January 2005   February 2005   March 2005   April 2005   May 2005   June 2005   July 2005   August 2005   September 2005   October 2005   November 2005   December 2005   January 2006   February 2006   March 2006   April 2006   May 2006   June 2006   July 2006   August 2006   September 2006   October 2006   November 2006   January 2007   April 2007   May 2007   June 2007   November 2007   December 2007   January 2008   March 2008   June 2008   February 2009   June 2009   February 2010   November 2010  

Quick index to blog-posts I like (from my personal website)

This page is powered by Blogger. Isn't yours? Statscounter is generating statistics of this page