[Dylan16807]

Substitute the N? No, you can't substitute "try every solution simultaneously" by "some kind of sampling".

Let's use a very simple example. How could sampling help you find the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4?

[cinquemb]

You couldn't sample from anything if the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4 is never used to encrypt any text. Though if the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4 goes on to be used to encrypt any text, and one has access to the cipher text, then you can sample from the cipher text.

[Dylan16807]

Okay, so you can't design anything for my example problem? It's not being used to encrypt anything, all you get is the hash. Which is solvable very very fast with an NP machine. If you can't apply your idea to that, you haven't found a general solution.

[cinquemb]

Yeah, a general solution wouldn't be useful in the wild against keys that are never used in the probabilistic approach i am thinking of, observations of cipher text are needed (which isn't unbounded).

[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.