[Computational Complexity] When is a theorem really proven?
- One of the comments on this blog pointed out correctly that for a theorem to be accepted by the community is not a Eureka Moment. It is a social process. The author of the comment was probably alluding to an excellent article by DeMillo and Lipton that I blogged about here. I highly recommend reading the article that blog points to.
We often say or write things like
- In 1978 Yao proved that if you store n elements of U in a table of size n then (for large U) membership requires log n probes (Ref FOCS 78).
- In 1981 Yao proved that if you store n elements of U in a table of size n then (for large U) membership requires log n probes (Ref JACM 81).
- In his FOCS 1978 paper (see also Journal version in JACM 1981) Yao proved the following:
- In his JACM 1981 paper (original in conference version in FOCS 1978) Yao proved the following:
Was Time Magazine right to say that the Fund Lemma was one of the big Science Stories of 2009 even though the paper was written in 2004? I think so- acceptance in a journal seems like a good time to declare YES THIS IS TRUE. And I do not know an alternative.
Posted By GASARCH to Computational Complexity at 1/25/2010 09:04:00 AM