Quote from: tromp on June 15, 2018, 12:12:36 PM

Quote from: aliashraf on June 15, 2018, 10:43:15 AM

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.

Yes, my mistake to call it NP-complete, it is NP. In the context of this discussion, when we refer to hash functions, the PoW problem (like one you have suggested, a conditional hash generating problem) is what we usually mean, yet I should have been more precise.

This was posted in a chaotic atmosphere but the point is maintainable that, verifying shares (not the Prepared block or its counterpart in traditional PoW, block) is a trivial job, by definition. Because it needs just verifying an answer for a NP problem.