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.
Also, the NP-hardness results would apply even if the Bitcoin algorithm is updated.
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. :)
I thought it was fun.
(If anyone with an identity and reputation thinks the grandparent posters comment has any merit at all, I'd be happy to talk it through with you and I'm confident that you'll be satisfied that they're talking nonsense. --- the harassing posts stalking me all over the internet is more then a little tiring)
That isn't true except on weekends, at least not for the last two years... there is usually a pretty healthy backlog available: https://people.xiph.org/~greg/temp/fee_avail4.png which is important for long term stability: https://medium.com/@bergealex4/bitcoin-is-unstable-without-t...
> and the knapsack problem disappears
Just cutting off low fee TX is a worse result than even the most approximate knapsack solver you could use. :) (Take transactions in order of fee per unit-limit, skip ones that won't fit, until you're full or you've skipped too many times sequentially-- which is what we do... with a too many threshold of a few thousand IIRC)
The reason for the floor is primarily to avoid wasting resources trying to verify transactions which are never going to confirm.
The floor rate used in the network today is 1e-8 BTC per byte, though it automatically goes up if the backlog of transactions gets large (over about 150MB of transactions). That limiting works by nodes keeping 150MB of transactions and if they gain more they drop the lowest feerate transaction and set their minimum to that value. The minimum then decays back to 1e-8 BTC/byte at a speed which depends on how much below the limit the node is...
[ these parameters don't need to be completely consistent in the network, nodes will tell their peers what fee levels they're willing to process]
> NP-hard conflict resolution problem
That is ignored in Bitcoin implementations today because double spends are rare, interesting ones are extra rare with complex dependency graphs, and there is a social good to behaving in simple an explicable ways.
Non-mining nodes have to implement a similar policy, as it's also used for preventing DoS on the P2P network.
We detached this subthread from https://news.ycombinator.com/item?id=14162653 and marked it off-topic.
Thanks for demonstrating that you're probably not even a Bitcoin user at all. (The median transaction size is 226 bytes, -- and so you're using a figure per kB-- so equal to 4.5 txn.)
(doubly ironic to see you complain about segwit in one breath and transaction fees in the next)
> people are waiting 6+ hours for a TX and are forced
You can choose how long you'd like to wait in exchange for more or less fees-- this how the system works, no one is forced to do anything.
> with a financial incentive to see Bitcoin fail
I have large incentives to see Bitcoin be successful-- but can you articulate any way that I can profit from failure?
I'm here writing to you with a well known identity, upfront about what I work on and what I think is important. If you're angry that other people won't rewrite Bitcoin's rules to suit whatever agenda you have-- that sounds like a personal problem. It certainly isn't my problem.