> This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

Could you back that up with some citations? This doesn't ring true. But my pure CS has withered a bit...