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