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

[Computational Complexity] Temporal Theory

Expand Messages
  • Lance
    One of our gradate students wanted to define a property P of classes C to hold if we don t know that C has complete sets. Doing so would make the concept time
    Message 1 of 1 , May 12, 2005
      One of our gradate students wanted to define a property P of classes C to hold if we don't know that C has complete sets. Doing so would make the concept time dependent. IP would have property P in 1989 but not in 1991 after we knew IP=PSPACE. One can easily show "If P=BPP then BPP has complete sets" but we don't have "If P=BPP then BPP has property P" rather we would have to say "If we know P=BPP then BPP has property P." Location can also be an issue. If the Martians have a proof that P=BPP then BPP has property P on Mars but not on Earth. Temporal Logic might give us a way to reason about such statements but basing them on unknown mathematical facts seems strange.

      Suppose someone proves the polynomial-time hierarchy collapses. Then it didn't collapse because it was always collapsed and in fact was never a true hierarchy. The only reason we call it a hierarchy today is because we don't know that it isn't.

      In mathematical reasoning we can't know whether a statement is true unless we have a proof of that statement. However once we have a proof of a theorem like P≠NP then not only do we have P≠NP now but in fact P≠NP was always true even before we had the proof. Despite this we can't help thinking that theorems become true as we see a proof. A year ago undirected connectivity wasn't in log space and now it is. However the theorems that were proven before I started graduate school were all true since the dawn of time.

      --
      Posted by Lance to Computational Complexity at 5/12/2005 01:12:00 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.