Bitcoin Mining is NP-hard (2014)

Re:Bitcoin Mining is NP-hard (2014) by Ar-Curunir on Thursday April 20, 2017 @10:28PM (#14162680)

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.

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by nullc on Thursday April 20, 2017 @11:51PM (#14162982)

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

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by pyromine on Friday April 21, 2017 @01:38AM (#14163329)

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

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by nullc on Friday April 21, 2017 @03:46AM (#14163761)

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

I thought it was fun.

[ Parent | on HN ]

[dead]

Re:Bitcoin Mining is NP-hard (2014) by indolering on Thursday April 20, 2017 @11:41PM (#14162951)

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.

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by nullc on Thursday April 20, 2017 @11:47PM (#14162969)

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 over the internet is more then a little tiring)

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by sanswork on Friday April 21, 2017 @04:55AM (#14164000)

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

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by null0pointer on Thursday April 20, 2017 @11:46PM (#14162967)

I'd love for there to be pure technical discussion however the development of most of the major cryptos boil down to political bickering at this point. What a sorry state of affairs :(

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by indolering on Thursday April 20, 2017 @11:57PM (#14163000)

There is nothing technical about that comment, s/he doesn't even preface it with a discussion as to what SegWit has to do with this post.

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by sanswork on Friday April 21, 2017 @04:51AM (#14163987)

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

[ Parent | on HN ]

Re:Bitcoin Mining is NP-hard (2014) by midmagico on Friday April 21, 2017 @12:10AM (#14163049)

You're using too many commas.

[ Parent | on HN ]