Hacker News Reader

Comment by cinquemb | Hacker News Reader

Probably very silly, but for a long time, when I've seen "p=np" thrown around, I've always considered it some kind of matrix math problem where n could be substituted by an identity matrix which itself could be substituted by some kind of sampling (which would represent observations of events bounded by np-space) unitary matrix multiplied by its conjugate transpose[0](thus, p = np -> p = ip -> p = uu*p, or p= u*up), which seems like that would be in line with a probabilistic method, is that the case? Or is this a wrong way to think about this?

[0] https://en.wikipedia.org/wiki/Unitary_matrix

View on HN

I don't understand what you mean. NP is not N multiplied by P, it is the name of a set, the set of all problems which can be solved by a Nondeterministic algorithm with Polynomial time complexity. P is the name of the set of all problems which can be solved by a deterministic algorithm with Polynomial time complexity. The P=NP problem is a set identity problem, it's not an algebraic equation.

Note that here nondeterministic algorithm can be thought of as an algorithm which can try every value in parallel when faced with any choice, even an infinite amount of values. For example, a nondeterministic algorithm can try every number in R in parallel. There is no known way to replace this nondeterminism with probabilistic methods.

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?

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.

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.

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

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.

Reply on news.ycombinator.com