<story><title>Why Philosophers Should Care About Computational Complexity (2011) [pdf]</title><url>http://www.scottaaronson.com/papers/philos.pdf</url></story><parent_chain></parent_chain><comment><author>stared</author><text>As an ex-physicist (quantum physics, now - data science), I am still puzzled why computer scientist consider computational complexity something metaphysical. Or even worse - a rule which universe should care about; look up considerations of non-local boxes and computational complexity (a generalization of quantum correlations; see Popescu-Rohrlich box).&lt;p&gt;First, even the CS&amp;#x27;s nightmare (where P=NP) may mean little practical difference (e.g. the simplest &amp;#x27;NP&amp;#x27; takes O(n^1000)).&lt;p&gt;Second, for many problems even O(n^2) is too much (think of big data problems). (Also, given that computation requires physical resources, you cannot scale it arbitrarily.) So even in P the actual exponent matters a lot.&lt;p&gt;One interesting, physical case is the spontaneous emission of a photon from an excited atom. It looks like an exponential decay, but the theory shows that the decay have to be polynomial (I don&amp;#x27;t remember it&amp;#x27;s power, if more like 1&amp;#x2F;t^3 or 1&amp;#x2F;t^6, but not too high). Up to my knowledge, we haven&amp;#x27;t detected the polynomial tail (because when it is, the probabilities are so low).&lt;p&gt;So, is there a physical effect that &lt;i&gt;cares&lt;/i&gt; about computational complexity? Or a phenomenon in which it matters that we can simulate it in &amp;quot;only&amp;quot; O(n^100), not O(2^n)?</text></comment>
<story><title>Why Philosophers Should Care About Computational Complexity (2011) [pdf]</title><url>http://www.scottaaronson.com/papers/philos.pdf</url></story><parent_chain></parent_chain><comment><author>eru</author><text>Also compare the The Ghost in the Quantum Turing machine (&lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;www.scottaaronson.com&amp;#x2F;papers&amp;#x2F;giqtm3.pdf&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;www.scottaaronson.com&amp;#x2F;papers&amp;#x2F;giqtm3.pdf&lt;/a&gt;) by the same author, and his marvellous blog at &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;www.scottaaronson.com&amp;#x2F;blog&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;www.scottaaronson.com&amp;#x2F;blog&amp;#x2F;&lt;/a&gt; .&lt;p&gt;There&amp;#x27;s also a slatestarcodex post about Scott Aaronson: &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;slatestarcodex.com&amp;#x2F;2015&amp;#x2F;01&amp;#x2F;01&amp;#x2F;untitled&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;slatestarcodex.com&amp;#x2F;2015&amp;#x2F;01&amp;#x2F;01&amp;#x2F;untitled&amp;#x2F;&lt;/a&gt;</text></comment>