Post
Topic
Board Development & Technical Discussion
Merits 1 from 1 user
Re: Getting rid of pools: Proof of Collaborative Work
by
tromp
on 15/06/2018, 12:12:36 UTC
⭐ Merited by anunymint (1)
SHA256 and other hash functions, are NP-Complete problems: their solutions consume negligible time and resource to be verified, it is basic in "computer science"  Wink

Hash functions are not decision problems, so they cannot be NP-complete.
I could create a decision problem out of a hash function though.
Something relevant for mining would look like:

The set of of pairs (p,y) where
  p is a bitstring of length between 0 and 256,
  y is a 256 bit number,
  and there exists an 256-bit x with prefix p such that SHA256(x) < y

Such a problem is in NP.
But it would still not be NP-complete, since there is no way to reduce other NP problems to this one.