Sunday, January 24, 2016
When do we stop giving the original reference?
I was preparing a talk which included my result that there is a sane reduction 4-COL \le 3-COL (the paper is here) when I realized that if I am going to claim the reduction is by Gasarch then I should find out and credit the person who proved 3-COL NP-complete (I assume that the result 3-COL \le 4-COL is too trivial to have an author). I could not find the ref on the web (I am sure that one can find it on the web, but a cursory glance did not yield it). The reference was not in Goldreich's complexity book, nor the CLR Algorithms book. I suspect its not in most recent books.
The reference is Stockmeyer, SIGACT NEWS 1973,
Few modern paper references Cook or Levin's original papers for the Cook-Levin Theorem. I've even heard thats a sign its a crank paper.
Few modern papers reference Ramsey's original paper for Ramsey's Theorem.
But the questions arises--- when is a result such common knowledge that a ref is no longer needed?
A result can also go through a phase where the reference is to a book that contains it, rather than the original paper.
On the one hand, one SHOULD ref the original so that people know who did it and what year it was from. On the other hand there has to be a limit to this or else we would all be refering to Euclid and Pythagoras.
Where does Stockmeyer's result fall? I do not know; however, I've noticed that I didn't reference him, and I will correct that.