P=NP? is such a difficult problem that it is more likely than not that a proof either way will necessitate extremely powerful new tools in complexity theory. It

P=NP? is such a difficult problem that it is more likely than not that a proof either way will necessitate extremely powerful new tools in complexity theory. It's hard to say what the impact on algorithm design and analysis would be.