[tsimionescu]

The point is this. Here is a nondeterministic algorithm that proves the problem the poster above was formulating is in NP:

  matching Passwords = choice(AllStrings, str -> hash(str) == desiredHash)

Assuming hash(str) has polynomial time, the nondeterministic algorithm above is clearly polynomial as well. Here `choice` is not a function, it is an elementary nondeterministic operation, one which evaluates the given function on each value in the input variable in O(1). AllStrings is the set of all strings, maybe limited to some max length if desired (otherwise, matchingPasswords will be an infinite set itself).

As far as it is known, there is no way to replace this with any sampling method that would take polynomial time. Of course, this is not proven, it is a related problem known as BPP=NP. BPP is the class of problems for which Bounded-error Probabilistic algorithms with Polynomial time complexity exist.