P=NP is best left to those who've devoted their lives to it, it's not really something one could sit down with one evening and solve. Of course, in this instance I'd be delighted to be shown wrong.
I'm not claiming I could solve it, or that it would be easy to solve. I do, however, like to have more than a cursory understanding of the "big" problems. My way of accomplishing that is to say, "OK, how would I solve this?" and give it a go.
In the process of doing that, I became convinced that P ~= NP. I will agree with you, however, that
if the answer is ever to be achieved, it will have to come from someone who dedicates their life to complexity theory. I emphasized the "if" because I also began to wonder: if the answer is P ~= NP can it ever be proven? I'm familiar with contra proofs, non constructive proofs, etc. But the nature of this one seems different. Why? For two reasons.
First, it seems the P = NP problem should itself be in NP. But as one tries to wrestle that possibility, it seems to me one becomes caught up in a Godelian type of incompleteness.
Second, for P ~= NP all one needs is a contra example. Take factoring as an example. The forward problem is multiplication, and it can easily be shown that multiplication is not reversible (or, at least, that one requires garbage outputs to make it reversible). To me that seems proof enough that there is no direct algorithm for factoring. One is forced to do a search of some sort, where factoring searches generally use a type of sieve. Given the way the non-polynomial times for those algorithms are expressed, one gets into the muddiness of what polynomial time really is. Is some algorithm with some exotic O(log log log n) type expression possibly polynomial or isn't it?
It's funny that it has been proven possible to identify prime numbers in polynomial time and yet the fastest algorithm currently runs better than polynomial time. What does that mean for P = NP?
Further, factoring has been proven possible in polynomial time using a quantum computer. What does that mean? Is P = NP even a relevant question anymore? I don't understand quantum computing very well, so I wonder if the probability function associated with them could be studied for some asymptotic feature that would associate them with deterministic computing to solve the problem that way. But maybe that's a stupid idea.
The bottom line is that this question intrigues me because of the similarity it seems to bear to Godel.
