## Monday, February 15, 2010

### 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.

1. I love the ads for this post! Two ads for psychic readings. Does anyone want to try to consult one of the advertised psychics for a second opinion to back up Bill's?

2. And I see Sarah for 2012.

3. Lyndon Johnson actually did run for a second term. However, he withdrew from the race after a suprisingly narrow victory in the New Hampshire primaries and the entry of Robert Kennedy into the primaries.

4. To clarify my Prez Question:
By NOT RUN I meant was not on the final ballot in November.

Thanks for the chance to clarify.

5. I predict that solving the P :: NP problem will be determined to be an NP problem, so we can finally go home, if finding home is not an NP problem.

6. i vote to impeach. where's the computational complexity. please quite or rename the blog.

all those in favor, please say aye.

7. they both took the oath of office in the white house itself

8. aye
specially if one is *not* an 'american'
for all I care, you should put palin on top, that will give more time for the rest of the world to develop while you stay in the darkness...

9. This is my prediction how p vs np will be solved

http://rjlipton.wordpress.com/2009/09/18/why-believe-that-pnp-is-impossible/#comment-2372

It's probably nonsense but at least
creative nonsense :-)