## True Names

Antonio Porreca:

Do waterfalls play chess? and other stories: After a brief introduction to complexity theory (Section 2), Aaronson turns his attention to one of the main cornerstones of this field, which is also one the points that are usually criticised: the relevance of polynomial time, as opposed to exponential time. Here he argues that this distinction is at least as interesting as the distinction between computable and uncomputable. Section 3.3 contains an interesting question that can be answered using a complexity-theoretic argument: why would we call 2

^{43112609}− 1 (together with a proof of its primality) a “known” prime, while “the first prime large than 2^{43112609}− 1” feels somehow “unknown”?