[btilly]

That is an argument for learning how to reason. Which is not actually the point under discussion. Going back to the parent of my comment:

> One thing I've frequently noticed in the rationalist community is the belief that if we all just reason hard enough, we'll reach the same conclusions.

What I'm showing is that results like https://www.sciencedirect.com/science/article/abs/pii/000437... demonstrate that this belief is incorrect. Two people starting with the same priors, same observations, and same views on rationality may do the best they can and come to diametrically opposed conclusions. And a lifetime of discussion may be too little to determine which one is right. Ditto putting all the computers in the world to work on the problem for a lifetime.

Real life is worse. We start with different priors and our experiences include different observations. Which makes stark disagreements even easier than when you start with an ideal situation of identical priors and experiences.

This result should encourage us to have humility about the certainty which can be achieved through rationality. But few rationalists show anything like that form of humility.

[lostmsu]

One of the good sides of NP is that you can validate it in polynomial time. So arriving to different conclusions is not a problem as long as you can recognize the reason.

[FreakLegion]

a) You can verify that a solution is valid in polynomial time, but you can't verify whether or to what extent it's optimal. But even if this weren't the case...

b) The solution you're talking about is an update to the network. It's buried back in the network's construction, not directly visible in the network itself. Model "blame" is a thing, but not heavily researched or at all cheap, computationally.

That said, btilly's "getting an approximate probability answer that is within 49% of the real one, is NP hard" isn't exactly true either. That's a description of what it takes for an approximation algorithm to guarantee some factor, i.e. set a worst-case bound. In practice an approximation can still be nearly optimal on average.

I agree with the broader point, though.

[btilly]

True, there are lots of cases where an approximation can create provably good answers question. But they usually require things like having probabilities bounded away from 1 and 0.

Unfortunately in the real world we actually are certain about lots of things. And when you add data, we tend to be more certain of previously uncertain things. Therefore we wind up with self-referential networks of beliefs that reinforce each other.

But sometimes there are two very different networks of beliefs, both of which are self-reinforcing. And a single data point can flip between them. Identifying which one is computationally impossible. However when you encounter someone whose beliefs are very different, and you can find the feedback loops that draw each of you in different directions, there is a good chance that the differences between you cannot be resolved by pure logic alone.

[FreakLegion]

I mean cases where the approximation isn't provably (or at least proven) good, but is still good in practice. This isn't uncommon with NP-hard problems or algorithms with bad worst-case behavior more generally, e.g. the Horspool variant of Boyer-Moore, or PCRE. It only takes one pathological case to wreck your guarantees, but those cases may be rare or even nonexistent in the real world.

Of course you actually could prove better bounds for an approximation algorithm given a specific universe of inputs. Your 'probabilities bounded away from 1 and 0' sound like an example of that (presumably the 'special cases' from the Bayesian network reference, but I only read the abstract). What I see more often are empirical studies showing, say, > 98% optimality for some kind of max cover approach to a specific problem, even though the guarantee in general is < 64%.

[btilly]

The problem is that both are approximate updates. Both verify in polynomial time that they are not exact. And neither knows how to find the real answer.

Polynomial validation isn't going to help.