For the record, this comment has motivated me to find some random introduction paper to computational complexity and slowly read and rewrite in my simplified own words as I go along.

Don't expect an actual LW post out of this, but (anyone can) feel free to bug/PM me in a few days to inquire on how it went. My hopes are that the mental muddiness around the subject will finally clear away if I try to explain it myself as I read it, even if I'm not explaining it to anyone in particular.