The Deutsch-Jozsa problem is a problem that quantum computers can solve deterministically, while classical computers cannot. However, there are classical algorithms that can solve it probabilistically. A simple example of such an algorithm is:
Check 500 inputs at random. If all of these inputs are equal, output "constant." Else, output "balanced."
This works because the probability of measuring all 0's or all 1's in a balanced function is $\frac{1}{2^{500}}$, meaning that the error is less than $\frac{1}{3}$. With the existence of this algorithm, Deutsch-Jozsa is in BPP.
And I would think that this also implies that the problem is in NP. But I can't find a (deterministic polynomial time) algorithm to verify if a solution is correct given some oracle and an output.