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.