Why Philosophers Should Care About Computational Complexity (2011) [pdf]
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).<p>First, even the CS&#x27;s nightmare (where P=NP) may mean little practical difference (e.g. the simplest &#x27;NP&#x27; takes O(n^1000)).<p>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.<p>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&#x27;t remember it&#x27;s power, if more like 1&#x2F;t^3 or 1&#x2F;t^6, but not too high). Up to my knowledge, we haven&#x27;t detected the polynomial tail (because when it is, the probabilities are so low).<p>So, is there a physical effect that <i>cares</i> about computational complexity? Or a phenomenon in which it matters that we can simulate it in &quot;only&quot; O(n^100), not O(2^n)?