P=NP

These CMU guys did the poll on P=?NP and totally forgot to call me.
May be the letter is in the mail but I am going to go out on a limb here and stating that it's going to be...wait for it

There, I said it! P=NP

Let's go all Nostradamus here. I know I am in minority here but I strongly believe this will happen; time-frame would be before 2050 and the techniques will involve high-order multidimensional reduction with sieve plucking. The exact technique used is currently unknown in the field and it better not be a algebric-geometric proof.

In coming years (2010-2019) we will have an example when there will be a polynomial time solution of SAT without knowing its complexity. Then we will actually have a proof before 2050.
May be that's what Knuth is going to talk about on June 30th, in his earthshaking announcement.

And hereby this sets a $0.01 bet premise with Jeff Bergman, adjusted to the inflation et al, who strongly considers P!=NP and he SHALL be proven wrong.

Ref:
SIGACT News Complexity Theory Column 36

Share