4 ms·
Does this also mean that Bitcoin mining time is quasipolynomial with the difficulty parameter?
by xiphias 10y ago
Does this also mean that Bitcoin mining time is quasipolynomial with the difficulty parameter?
- drdeca 10y agoI don't think bitcoin's work function is based on graph isomorphism?
- xiphias 10y agoYeah, I read more about it, only subgraph isomorphism is known to be NP-complete...of course the complexity of that will remain a mystery for a long time.
- wolfgke 10y agoAnd finding a nonce that makes the block have a SHA256 with many leading zeroes is probably not an NP-hard problem.
- xiphias 10y agoIt is, some people also tried SAT solvers for mining: http://jheusser.github.io/2013/02/03/satcoin.html http://jheusser.github.io/2013/02/03/satcoin.html
- wolfgke 10y agoPlease look up the definition of NP-hardness again. If the problem (#) := "finding a nonce that makes the block have a SHA256 with many leading zeroes" was NP-hard, it would be an interesting idea to use a solver for (#) to solve e.g. SAT (not the other way round!). TLDR: You talked about the wrong inclusion.
- ajkjk 10y agoNot even related.