[nullc]

> The current default Bitcoin implementation makes no effort to solve or even really approximately this problem

I think this was somewhat out of date even when it was written. :(

When I've sampled it before the solver in Bitcoin reliably produces results which are very close to the best results that an external MILP solver produces... and since a year and a half ago it even considers dependencies in that analysis.

The knapsack part of the problem is not that impacting because a block is composed of thousands of transactions, which are mostly very small compared to the block size... and for the lower fee transaction the slope of the fees per unit for the available options is not very high. Basically, so long as you get the high fee transactions it usually doesn't much matter if you fail to eek the last few bytes out of a block.

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