Is factoring in P?
One of the most interesting answers was
I don't really see why it shouldn't be. - Peter Shor
Recall that Peter Shor proved Factoring is in Quantum-P which lead to intense interest in Quantum Computing.
1) What if factoring was in P and this was shown before Shor's algorithm? Would Shor or someone else have ever proven factoring in quantum P? Would there be as much intense interest in quantum computing as there is now? Perhaps by physicists more than CS people?
2) What if factoring was in P and this was shown before RSA? Where would crypto be now? Zip drives with a googleplex random (or nearly random) bits and more 1-time pads? More lattice based crypto? Or RSA but with larger numbers? This may depend on how good the factoring algorithm is.
3) More generally, how much does the order of events matter for science?
a) If the Banach-Tarski paradox was discovered early on, would we have just tossed out the Axiom of Choice before so much more was build on it? Darling thinks we should toss out AC NOW because of Banach-Tarski.
b) In the model of set theory L you can do ALL of math except some parts of set theory and maybe a few other things (note quite: Harvey Friedman has found some combinatorial statements that need large cardinals to prove). Had L been discovered earlier then could we all now be working in L (except a few people who look at other models, but they are not in the mainstream)? We might know more about L and less about forcing. We would KNOW that AC and CH are true. Or we would think we know.
c) If Engineers were the first ones to look at SAT and reductions, might they have been content to know that if SAT \le A then A is probably hard? No need for the Cook-Levin Theorem! And then when someone proved Cook-Levin would the Engineers not really cares since they already knew SAT was hard?
d) I can imagine Ramsey's Theorem being discovered much later for some application, or perhaps never being discovered at all.
e) VDW's theorem has so few application, I can imagine it never being discovered.
4) There are cases where if A was discovered before B then B has an easy proof, whereas if B was discovered before A, then B has a hard proof. I'll give one example:
Given HALT is undecidable, Godel's theorem is easy.
Assume HALT is undecidable.
Let STAT(e) be the statement M_e(0) does not halt.
There is some e such that M_e(0) does not halt but ZFC cannot prove this.
PROOF: Assume, By Way of Contradiction that for all e such that M_e(0) does not halt,
ZFC could prove this. Then HALT is DECIDABLE:
Given e, run M_e(0) and at the same time enumerate all proofs in ZFC. It is guaranteed that
you will either find M_e(0) halts or a proof that M_e(0) does not halt. Hence you will,
in finite time, know if M_e(0) halts OR NOT.
END OF PROOF
Is the sequence of events where HALT is proven undecidable before Godel's theorem plausible.
I think so
I INVITE my readers to give there own examples of when Math is not commutative- meaning that
the order of events matters.