[Computational Complexity] Prediction on Presidents Day
- Its PRESIDENT"S DAY so I have two predictions: One about the election of 2012 and one about P vs NP.
ON P VS NP: I have one prediction about P vs NP. It is not about when it will be solved (though I think this will be a long time). Look at the separation NC1 ≠ AC0. This was NOT achieved by taking a problem complete for NC1 (the word problem for S5) and showing it is not in AC0. Instead a different problem in NC1, PARITY, was shown to not be in AC0 (CHECK- is it known that PARITY is NOT complete for NC1? I think so - PARITY can be done in width 2 , poly sized BP and NC is equivlaent to width 5 poly sized, is probably the main part of the proof.)
I predict that P ≠ NP will be proven by showing some problem that is in NP but NOT NPC is not in P. The NPC problems seem to be hard to prove things about. Hence a problem in NP but not NPC may be better. Factoring is a candidate for this. Graph Isom may also be a candidate--- its like PARITY in that its very delicate. But it may very well be in P.
ON THE ELECTION OF 2012. For the Prez election of 2008 I predicted, before the primaries, that the candidates would be Barak Obama and John McCain, and that Barak Obama would win. I never blogged about it so my readers may be skeptical that I made such a prediction. Hence I will, today, predict the nominess for 2012: Barack Obama and Mitt Romney.
Barack Obama is obvious- TRIVIA- The last president to decline to run for a second term was LBJ. Note that he originally got to be Prez because he was VP when JFK died. The one before that was Harry Truman. Note that he originally got to be Prez because he was VP when FDR died. Who was the last president who obtained office NOT be being VP when the Prez died, who did not run for a second term? MORE TRIVIA:Call this prez X. Give a non-trivial trivia question for which the answer is Barack Obama and X. (I will answer these at the beginning of my next post.)
Mitt Romney- The republicans tend to give the nomination to someone familiar to them. Like the guy who came in second last time. Palin is also familiar to them, and she may run in the primaries, but I do not think she will get the nomination.
I also predict that Obama will win.
Posted By GASARCH to Computational Complexity at 2/15/2010 01:17:00 PM