Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] When is a theorem really proven?

Expand Messages
  • GASARCH
    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
    Message 1 of 1 , Jan 25, 2010
    • 0 Attachment
      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
      1. 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).
      2. 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).
      Personally I try to include both the conference and the journal version in a citation. That solves the citation problem. However, what does prove mean? It could be that Yao proved this in 1977. The exact time/day/year when something is proved is not that well defined. The original post was about the Fund Lemma where the paper was written in 2004 and accepted in 2009. What was its status in 2006? Proven or unproven? Is there a better way to say these things?

      1. In his FOCS 1978 paper (see also Journal version in JACM 1981) Yao proved the following:
      2. In his JACM 1981 paper (original in conference version in FOCS 1978) Yao proved the following:
      These both sound awkward. I am willing to live with using proved even though its not quite right. Does someone have an alternative?

      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
    Your message has been successfully submitted and would be delivered to recipients shortly.