[Ar-Curunir]

I'm sure you know this, but NP-hardness results only matter for worst-case instances. Even if Bitcoin's algorithm is roughly close to optimal on real-world instances, it doesn't mean somebody won't be able to generate a series of transactions that cause the algorithm to exhibit worst-case behaviour.

Also, the NP-hardness results would apply even if the Bitcoin algorithm is updated.

[nullc]

Oh sure, I wasn't intending to comment on the NP-hardness but only on the accuracy of the approximation in practice.

There is a lovely paper disproving the all-public-information efficient market hypothesis, assuming computationally bound actors by showing how to embed market inefficiency into a set of trades that can only be removed by solving a NP-hard problem. :)

[pyromine]

Do you remember the name of the paper, that sounds like a fascinating paper

[nullc]

I dug it up for you: https://arxiv.org/abs/1002.2284

I thought it was fun.