[Computational Complexity] Temporal Theory
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