Computational intractability and reductionism?

Question

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?

Answer 1

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.

Answer 2

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).