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.
(#) := "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.