Tuesday, August 24, 2010

[jijsvmow] P not equal to NP proof idea

"If P=NP, then life is not worth living."

"Oh really?" I challenge:  What if P=NP because 3SAT is solvable by a polynomial time algorithm with exponent n, where n is the largest finite integer that has ever appeared in a serious mathematical proof, making Graham's number look minuscule.  Moreover, this bound is tight (big Theta); that is, this horrible yet polynomial algorithm is provably the fastest algorithm that can solve 3SAT.  Is life still not worth living then?  (There would still exist fortunes to be made and adventures to be had with fast approximate solutions to NP problems.)

But 3SAT (or perhaps some other NP complete problem) is just a simple-looking problem.  How could such a problem cause such huge but finite exponent?  There doesn't seem to be enough "rope", enough levers or buttons to push.  It's sort of the same feeling as the Busy Beaver problem; when only limited to a certain number of states, there is the maximum unary number a Turing Machine can emit.

So, instead of asking whether there is exists a polynomial time algorithm that will solve 3SAT, let's consider all polynomial time algorithms that will compute any "interesting" property on a general 3SAT instance, moreover, minimal algorithms: there exists no other algorithm with lower exponent that will calculate the same property.

Put an information theoretic bound on the property.  Otherwise, with more and more complicated properties, one could require arbitrarily complicated algorithms.

Finally, among all these algorithms, what is the highest exponent achievable?  In other words, what is the largest big Theta algorithm that computes anything "interesting" about a 3SAT instance?  If such a bound exists, then it becomes less likely that P=NP, because we could enumerate, maybe(?), all algorithms less than that bound and see if any of them solve 3SAT.  If no such bound exists, then this proof idea seems useless.

Taking a wild stab in the dark, perhaps the highest exponent algorithm computes whether a given instance of 3SAT is isomorphic (in some way) to the Fischer-Griess Monster group, with exponent equal to the huge order of the Monster group.  But beyond the Monster group, there are no more complicated "simple" questions, so it's the end of the line.

No comments :