Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bitcoin Mining is NP-hard (2014)

freedom-to-tinker.com

Post reply on HN
Print view View original

21–27 of 27 posts

Re: Bitcoin Mining is NP-hard (2014)

#21

Post by pyromine »

nullc wrote: post #14
Ar-Curunir wrote: post #8

Earlier quoted context omitted.

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.

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. :)

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

Re: Bitcoin Mining is NP-hard (2014)

#22

Post by nullc »

pyromine wrote: post #21
nullc wrote: post #14

Earlier quoted context omitted.

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. :)

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

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

I thought it was fun.

Re: Bitcoin Mining is NP-hard (2014)

#23

Post by nullc »

dang wrote: post #20
replies_to_all wrote: post #9

> That isn't true except on weekends, at least not for the last two years... there is usually a pretty healthy backlog available... Are you insane, Sir? Right now (Thursday) people are waiting 6+ hours for a TX and are forced to use TX accelerators just to get a TX through [1]. Average cost per TX is over $2.00 right now [2], BECAUSE of the backlog. Nullc, you are a jackass with a financial incentive to see Bitcoin f…

We've banned this account for breaking the HN guidelines. Doing this will eventually get your main account banned as well, so please stop. We detached this subthread from https://news.ycombinator.com/item?id=14162653 and marked it off-topic.

Any interest in sharing the identity of the apparent primary account? It would be very helpful to my sanity and personal safety to know more about the persons stalking me around and harassing me online...

Re: Bitcoin Mining is NP-hard (2014)

#24

Post by sanswork »

replies_to_all wrote: post #10
Ar-Curunir wrote: post #8

Earlier quoted context omitted.

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 is CTO of a company trying to take control over Bitcoin development by pushing an update they call "SegWitness". Nullc's gamble is that if they can get their code into Bitcoin their company, Blockstream, will be able to sell their "expertise". Honestly, at this point, they are just a marketing company with a single product they are desperate to push at any cost. If nullc does not seem to "understand" something,…

Surely nullc's company could sell their expertise even without segwit getting pushed given the number of core developers on their payroll?

Re: Bitcoin Mining is NP-hard (2014)

#25

Post by sanswork »

nullc wrote: post #13
indolering wrote: post #11

Earlier quoted context omitted.

Can we please leave the cryptocurrency drama out of this? Every time a cryptocurrency post is submitted to HN the discussions get overtaken by political bickering.

The more pseudonymous shill hate-posts that get made the faster the jerks funding people to attack like this run out of funds. I celebrate everyone one of them. (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…

Sadly I don't think there is any risk of them running out of money anytime soon.
Post reply on HN