Bitcoin mining is NP-hard

Misleading title.<p>The article talks about how choosing the optimal set of transactions to include in a block is NP-Hard, and the typical implementation uses a simple greedy approximation.<p>But I <i>thought</i> I was going to read about someone doing a security proof showing that a fast way to generate blocks and extend the chain would give us a polynomial algorithm for 3-SAT. Which would have been awesome.

Optimal blocks aren&#x27;t really a priority for miners because the fact that you win the race is worth, ballpark, 250X (the coinbase transaction&#x27;s segniorage award of 25 BTC) what the transaction fees for the transactions included in the block is. Optimizing for a few percent extra transaction fees doesn&#x27;t meaningfully change the economics, and if it slows you appreciably, could potentially cost you that segniorage if someone else beats you to the punch.<p>Accoringly most miners appear to just use really cheap heuristics.

&quot;but this formula has other benefits as it enforces minimum transaction fee amounts&quot;<p>Why is this good&#x2F;important?

Unfortunately, the problems he reduces from are not so hard in practice. Knapsack has what&#x27;s called an FPTAS, which means you can get as good an approximation as you want, and the runtime only scales polynomially with your desired accuracy. And independent set has nice approximation algorithms for bounded degree graphs and other restricted graph classes (though there is no general constant-factor approximation unless P = NP).<p>So it&#x27;s funny that the author quotes knapsack as the possible true difficulty...