Do you still win the 1 million dollars if you show that P=NP (and thus P!=NP) is unprovable, as opposed to equal or unequal?
Name:
Anonymous2010-01-01 10:53
>>6
Or find an algorithm which solves most or all practical instances of an NP-complete problem in P time, and yet there would still be instances which take an exponential amount of time. i.e. prove that all NP-complete problems are NP-hard.
Also, that situation would be extremely disappointing for the person who found the algorithm.