Tayzwi
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:
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:
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?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.
Labels: computer science, research
posted by Tejaswi # 4:59 AM 
Comments:
<< Home
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?
More than the patience it is about a "gut feel" and a motivation which comes with a familiarity (which can be experienced at the beginning or somewhere down the lane) while studying a problem which makes a mathematician/scientist set to disprove something. Exceptions to rules are not a good thing....There are more like Kabaab mein haddi...But if there are too many exceptions, the rule itself may be screwed up.
The bottomline is if you try to "generalize" a counter-example, there could be a counter-example to a counter-example (which can be called a counter-counter example??).
PS:- I am not drunk.Sumne timepass ge barde.....
More than the patience it is about a "gut feel" and a motivation which comes with a familiarity (which can be experienced at the beginning or somewhere down the lane) while studying a problem which makes a mathematician/scientist set to disprove something. Exceptions to rules are not a good thing....There are more like Kabaab mein haddi...But if there are too many exceptions, the rule itself may be screwed up.
The bottomline is if you try to "generalize" a counter-example, there could be a counter-example to a counter-example (which can be called a counter-counter example??).
PS:- I am not drunk.Sumne timepass ge barde.....
Your post reminded me of something I read elsewhere. Someone recently disproved the Riemann hypothesis. So he wasn't that great a mathematician huh?
Similar experience with reductions. Coming up with the widget for the hamiltonian or from 3-SAT to vertex cover.
Non-Euclidean geometry anybody :).
Non-Euclidean geometry anybody :).
There is an urban legend about a professor (some say he is none other than Prof Diwan). An undergraduate was giving a seminar and the prof was in the audience. The student made a cavalier claim of some sort which the prof was not comfortable with. After about 30 seconds, the prof stood up and drew a 17-node weighted graph to disprove the claim.
Not as good as Tutte's polyhedron, but impressive none the same.
Rahul
Not as good as Tutte's polyhedron, but impressive none the same.
Rahul
There is an extremely celebrated book devoted to counter examples in topology by Steen and Seebach. Although I don't think it relates to graph theory (or TSP, for that matter) in any sense, but it deals with a more general subject -- topology.
The bigger question is, don't examples suffice? Why do we need counter-examples? Examples show us that we can get some wok done. So "let's get it done", with apologies to Citigroup. If our algorithm cannot get something done, let's try a trick older than mathematics - money! If we cannot solve the traveling salesperson problem, let's ask him not to travel - we can establish retail outlets, start selling online or organize a customer event where potential customers travel, wine, dine and hopefully write a check.
Pragmatism aside, I do realize that the traveling salesperson problem is an important problem that's better solved than unsolved. So let me make an effort propose a solution. Since the traveling salesperson problem is NP hard (I got to know what it means, courtesy you), can we not make the hardware that executes the NP hard algorithm scale up as the number of nodes scales up?
Pragmatism aside, I do realize that the traveling salesperson problem is an important problem that's better solved than unsolved. So let me make an effort propose a solution. Since the traveling salesperson problem is NP hard (I got to know what it means, courtesy you), can we not make the hardware that executes the NP hard algorithm scale up as the number of nodes scales up?
>> a minimum spanning tree over the vertex set wouldn't give us a minimum Steiner tree
why one hour? take a triangle ABC with edge weights AB=1, BC=1, AC=3. min spanning tree of {A,C} is of cost 3 where as min steiner tree over {A,C} is of cost 2.
Did I understand the question wrong?
Post a Comment
why one hour? take a triangle ABC with edge weights AB=1, BC=1, AC=3. min spanning tree of {A,C} is of cost 3 where as min steiner tree over {A,C} is of cost 2.
Did I understand the question wrong?
<< Home
Archives
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)
