What is the complexity class of solving hash decision problems? With $hash_n$, I mean a standard cryptographic hash like sha256, scaled up to have arbitrary length $n$ of its output with the same underlying principles. What is the time complexity class of the following problem?


  Given an $n \in \mathbb{N}$ and data $d$ with $length(d) = n$, determine whether $\exists p : ((length(p) \le n) \wedge (hash_n(p) = d))$.


I find it really hard to find a class for it because it seems like a hard problem and it's definitely not $\in P$ (except if $P = NP$ or there is a vulnerability of the hash function (assume there isn't one not already known (so sha256 basically just printing the state of a state machine can be used, of course))) but you can't use it to solve any of the classical NP hard problems.

Determining the space complexity is of course trivial: It's only $\mathcal{O}(n)$.

This is of course just one example of a hash decision problem and it's meant to only be an example. I'm more interested in the general classification of hash decision problems.

Edit: You may assume a perfect hash function instead of a commonly used cryptographic hash function. E.g. if you're more comfortable with it, you don't want to exploit properties of cryptographic hash functions which are commonly used in practice, what you want to show is threatened by those properties, etc.
It's in NP.  In particular, it is easy to provide a witness for a yes answer (the witness is such a value $p$) and given a witness, you can verify the yes answer in polynomial time.

As you say, it's not in P if the cryptographic hash function is cryptographically secure.

I don't think it's likely to be NP-complete, but at the moment I can't articulate a specific reason why I think that.

(If you have a one-way permutation, then it's in NP $\cap$ coNP, so unlikely to be NP-complete... but that doesn't apply to your question.)