It seems straightforward to argue that if the variables of one physical (or biological) theory A are shown to be uncomputable (in the Turing sense) as a function of the variables of another physical theory B, and the Church-Turing thesis holds, then A is not reducible to B, and we would have a strong argument against reductionism.

But what about the case where the quantities of A were computable in terms of quantities from B, but such that they were computationally intractable (as in NP-hard). This is the case for certain spin-glass problems and for protein folding problems. Assuming P != NP holds, does this computational intractablitiy amount to a refutation of reductionism? My questions:

  1. Does the computational intractability of certain quantities in terms of lower order quantities constitute a refutation of reductionism?
  2. Or does the fact that, even though computationally hard, we still have heuristics for reasonable approximation of these quantities or heuristics that require reasonable amounts (i.e. polynomial) of time in the average case, mean reducibility in the physical sense still holds?
  3. Can one classify anti-reductionist stances into “strong” anti-reductionism based on Turing uncomputability and “weak” anti-reductionism, based on NP-hardness?
  • (a) why would you think in the first place that computational complexity should or might have any bearing on reducibility of physical theories? (b) why do you mix turing reducibility with the reducibility of physical theories? what is the relation between the two senses of reducibility? for example, is there an important relation between going to work at the office and doing work on an object by pushing it?
    – nir
    Commented Nov 10, 2015 at 19:56
  • Spin glass might not be a good example here -- in spin glasses a problem is that the macroscopic quantities (e.g. susceptibility) cannot be predicted (for a given sample) without the microscopic details; c.f. the final section here arxiv.org/pdf/1508.03368
    – Dave
    Commented Nov 10, 2015 at 19:59
  • @nir (a) if it's too difficult to compute then is it really reducible? (b) That's pretty much the gist of Deutsch's strong version of the Church-Turing thesis, the so called the Church-Turing-Deutsch thesis Commented Nov 10, 2015 at 20:21
  • This sounds similar to weak vs. strong emergence, but your NP-hard "non-reductionism" is even weaker than weak emergence. The only reductionism it excludes is what Anderson calls constructionism, "ability to start from those laws and reconstruct the universe". en.wikipedia.org/wiki/Emergence#Strong_and_weak_emergence
    – Conifold
    Commented Nov 10, 2015 at 22:55
  • I already got the sentiment "if it's too difficult to compute then is it really reducible?" from your original post - so you are merely reiterating it - I am asking what justifies it, except for a play of words? why don't you lay out the sense of reduction you are attacking in more detail, and maybe then it will naturally become clear if computational complexity has anything to do with it at all - I do not mean to offend, but as it is the question seems to me a little bit like stoner philosophy; if you have an idea in mind, lay it out in more detail - don't leave all the work for us.
    – nir
    Commented Nov 11, 2015 at 10:43

2 Answers 2


I would argue that there is a place for the complexity of a reduction to matter, but that we do not use it in determining whether there is a reduction.

Let's take a concrete example: we consider Newtonian dynamics to be reduced to the Schroedinger equation, and we can convince ourselves of this deduction with some efficiency. But the efficiency is the efficiency of verifying coverage of the behavior, not of actually doing the reduced field in terms of the more basic one.

But that means this is, intrinsically a verification, i.e. an "NX" problem, and P vs NP is not part of the way we should look at this complexity. We do not need to solve the old domain in the new one, only to believe the math that proves coverage. We also generally don't measure the complexity of a proof in orders of magnitude. We expect such proofs to be finite. (So that makes question 3 silly.)

So even though the reduction does not give us a tractable way of computing the higher-order behavior from the lower-order behavior, we consider the problem reduced. But we do consider these two scopes to be different domains of physics. We do not attempt to take Newtonian measurements in quantum terms. (The same it true of thermodynamics, we do not measure temperature in terms of average speeds of particles, we use distributions and move away from actual kinetics as a basic approach. And of astrophysics, where we realize we need to attend to relativity.) I would argue that this is the point at which complexity matters.

We consider the opposite reduction impossible. Because we can do something like the deBroglie or Bohm reduction, which breaks things up in terms of moving waves shaped by standing ones, or particles directed by waves, and so uses Newtonian terms. But we find an infinite regress trying to pin down "the phase of the particle's wave", or "the location of the particle being guided". The to zoom in produces more and more unknown Newtonian velocities, which we cannot compute without global information. We can't be sure those values actually exist, so we generally don't consider this a reduction.

Again, the complexity is irrelevant to whether or not there is a reduction. It does not matter whether or not the deterministic under-model would be staggeringly complex, only that it is in principle circular.

This latter case gives a good example of your question 2, and the answer is that it depends who you ask. Different people look at this in either of the ways you suggest.

If a simulation is not good enough, we can back away from the complexity by simply not considering things reduced, and imagine a basic lack of similarity between the systems. If a simulation is good enough, we can say the values theoretically exist, but are 'hidden', and their values can never be known, but we can choose values in our simulation, and it works. (We even know how close we can get to knowing them, in principle, if they do exist, and why.)

So we can claim that there is a deterministic model, though not a reduction to it, or that there is none at all.


There are several meanings for "reductionism" that people apply. However, in philosophy "reductionism" typically means "ontological reductionism," the idea that A is B. For this particular meaning, computational complexity does not figure into their thinking. Either A reduces to B, or it doesn't (such as if the reduction would require a computational solution to an uncomputable function).

There may be one additional demarcation, provability. Some may claim a reduction from A to B, but be unable to prove it. This is certainly weaker than a provable reduction from A to B.

That being said, if one looks at it from a utility point of view and asks "does this reduction provide value," computational complexity or difficult identifying initial states (such as in spin glass), it may be that a reduction provides no value, even if it is ontologically true. Likewise, there may be reductions that do provide value, but are not ontologically true (such as simplified physics models).

  • But that's the real gist of my question: What's the good of ontological reduction if I can't actually calculate anything with it? Commented Nov 10, 2015 at 20:32
  • I find that question to be a very useful question. I tried to provide more shades of grey in my answer to support varying beliefs about its answer. Some would argue to death the value of reductionism, and some would argue to death against it. However, from the utilitarian perspective it certainly suggests that the value of such knowledge is dependent on how you may use such knowledge after it has been acquired.
    – Cort Ammon
    Commented Nov 10, 2015 at 22:00
  • I will add that some ontological reductions could have value from a utilitarian perspective. If such a reduction smoothly transitions between modeling B and modeling A in B, it can be used to avoid the age old question of "where does A end?" It can permit a flexibility in the handling of A that can be tricky without a clear transition from A to B. However, the value of such an ontological reduction is not automatically higher than that of a less-than-ontologically-true reduction (such as a simplified model). Sometimes the simple model can have more value, thanks to simplicity.
    – Cort Ammon
    Commented Nov 10, 2015 at 22:12
  • (your results may vary, depending on how one arrives at a utility function to be applied to the theories in question)
    – Cort Ammon
    Commented Nov 10, 2015 at 22:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .