Chapter 12: The Principle of Computational Equivalence

Section 10: Intelligence in the Universe

P versus NP [and messages]

Given a constraint, it may be an NP-complete problem to find out what object satisfies it. So it may be difficult to generate the object from the constraint. But if one allows oneself to generate the object in any way at all, this may still be easy, even if P != NP.

From Stephen Wolfram: A New Kind of Science [citation]