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.
Subscribe to:
Post Comments (Atom)
Many times it happens the proof of a theorem commonly known is different from the first publisher and remains unacknowledged. What is your opinion on that? Should a text book or paper refer to the paper that give the proof included for illustrative purposes?
ReplyDeleteOn the one hand YES, refer to the original proof AND the common proof AND point this out. On the other hand there is a limit to how far back you want to go with this.
ReplyDeleteI was under the impression that this was shown independently by Lovasz and Stockmeyer.
ReplyDeleteL. Lovasz. Coverings and colorings of hypergraphs. In Proc. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, Winnipeg, pages 3--12, 1973.
L. Stockmeyer. Planar 3-colorability is polynomial complete. ACM Sigact News, 5(3):19--25,1973.
THANKS, I have added the following refs to my paper (on arXiv)
DeleteKarp- who proved { (G,k) : G is k-col } NPC
Lovasz and Stockmeyer who showed COL_3 is NPC.
As the paper title above indicates, Stockmeyer actually showed
Planar 3-col NPC.
While these results are all well known and perhaps do not need
to be referenced (1) WHO did them is not that well known, and
(2) my paper was DIRECTLY on graph coloring and depended, contrasted, to prior work, so appropriate to give orig refs.
Is your reduction parsimonious? (weakly or strongly)
ReplyDeleteI Googled "Strong parsimonious reduction" and got nothing hence
Deletethis concept does not exist :-) Seriously, I think you mean
STRONG- if G has L 4-colorings then G' has L 3-colorings,
WEAK- if G has L 4-colorings then G' has f(L) 3-colorings
where f has some properties.
Anyway, I doubt my current reduction does, but I am sure it
can be modified to be weak pars.
People in physics still keep citing the AdS/CFT paper from 1997 (see number 1. here: https://inspirehep.net/info/hep/stats/topcites/2014/alltime.html) when it is incredibly well-known and now has over 10k citations. If you don't know Madelcena's paper and are working on AdS/CFT, it's like working on quantum mechanics and not knowing what role Bohr played. (not sure that's an exact analogy, as QM is experimentally observed!)
ReplyDeleteBut that's not the worst: in biology people still cite a paper from the 1950's that invented a standard technique (see http://www.nature.com/news/the-top-100-papers-1.16224), which all students would know and study. It's not like we have to cite Newton and Leibniz when we use calculus...