> A plausible proof of "P != NP" won't be quite as simple to express, since it needs to prove that all such algorithms do not run in polynomial time.

That sounds hard but, If for any NP-Complete problem there exists no P solution then for all NP problems there is no P solution. So this proof sounds like it has the right shape.