Graph Isomorphism update: quasipolynomial claim restored

Re:Graph Isomorphism update: quasipolynomial claim restored by xiphias on Monday January 09, 2017 @10:45PM (#13362389)

Does this also mean that Bitcoin mining time is quasipolynomial with the difficulty parameter?

[ Parent | on HN ]

Re:Graph Isomorphism update: quasipolynomial claim restored by drdeca on Monday January 09, 2017 @11:45PM (#13362654)

I don't think bitcoin's work function is based on graph isomorphism?

[ Parent | on HN ]

Re:Graph Isomorphism update: quasipolynomial claim restored by xiphias on Tuesday January 10, 2017 @05:41PM (#13369895)

Yeah, 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.

[ Parent | on HN ]

Re:Graph Isomorphism update: quasipolynomial claim restored by wolfgke on Tuesday January 10, 2017 @05:46PM (#13369940)

And finding a nonce that makes the block have a SHA256 with many leading zeroes is probably not an NP-hard problem.

[ Parent | on HN ]

Re:Graph Isomorphism update: quasipolynomial claim restored by xiphias on Tuesday January 10, 2017 @06:48PM (#13370427)

It is, some people also tried SAT solvers for mining:

http://jheusser.github.io/2013/02/03/satcoin.html

[ Parent | on HN ]

Re:Graph Isomorphism update: quasipolynomial claim restored by wolfgke on Tuesday January 10, 2017 @07:46PM (#13370779)

Please 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.

[ Parent | on HN ]

Re:Graph Isomorphism update: quasipolynomial claim restored by ajkjk on Tuesday January 10, 2017 @12:48AM (#13362920)

Not even related.

[ Parent | on HN ]