What is missing for this P != NP proof?

Question

I tried to recover a password. When thinking of this I recognized that the problem "password recovery" is a very nice example of a NP problem. If you know the password it's very easy to verify it in polynomial time. BUT if you don't know the password you have to search the whole space of possible solutions which can be shown to take exponential time.

Now my question is: Doesn't this demonstrate that P != NP since "password recovery" is an element of NP that can be shown to require more than polynomial time to run?

Answer 1

Does just verification belong to the same class of problems as search?

Answer 2

NP does not mean "nonpolynomial", if that's what you were thinking (and my apologies in advance if you were not!). It means "nondeterministic polynomial". A nondeterministic algorithm is one that's equivalent to an unbounded number of parallel instances of an algorithm. As an example, finding the correct password by brute force is nondeterministic polynomial: if you imagine that checking the password, if your guess happens to be correct, takes linear (i.e. polynomial) time on the length of the password, but that you need to check an arbitrary number of possible passwords (k^n) in parallel, then the cost of finding the solution using this method is nondeterministic polynomial.

A nondeterministic algorithm can also be thought of one whose state branches at some steps. A simple example of this is a nondeterministic finite automaton (NFA) -- sometimes you don't know what edge to take between states, so you take them both. It's easy to show that every NFA is equivalent to a deterministic FA, and so it is tantalising to think the same could be proved for other interesting classes of algorithm. Unfortunately it's hard to do so for the general case of polynomial algorithm, and the general suspicion is that they are not equivalent, i.e. that P != NP.

Answer 3

The reasoning that the problem is in NP is correct: if it can be verified in polynomial time, it's in NP. Even very simple problems are in NP. Basically, all of P is included in NP. (*)

Now, here is one way you could go about turning this into a proof that P != NP:

1) Show that "password recovery" is NP-complete. That is, any problem in NP can be reduced to "password recovery" in polynomial time. (i.e. there is an efficient algorithm to convert any other NP problem to "password recovery".)

2) Once you have that then, as Pavel Shved mentions, it is not enough to show that the intuitive algorithm is non-polynomial. You have to show that there does not exist a polynomial algorithm to solve "password recovery". A very difficult task.

(*) Edmund is also right: NP means polynomial on a non-deterministic machine. A polynomial verification is essentially the path chosen by the non-deterministic machine.

Answer 4

The problem is not showing that password recovery is non-polynomial, since clearly it is -- you have to search an exponential space of answers.

Actually, "password-recovery" isn't really a description of a standard computational problem. It seems that, formally, password breaking algorithms take some sort of "oracle" that can answer whether a given string is the correct password. However, P and NP are defined in terms of Turing machines, which take strings as input.

Answer 5

1. As stated, "password recovery" is not a decision problem.
2. You have not proved that "password recovery" does not have a polynomial-time algorithm, you have merely argued on intuitive grounds that it does not. Just because a solution space is gigantic does not mean there are not fast algorithms to find the solution; for example, there are n! permutations of a set of n distinct integers but only one is sorted ascending yet we can find it in n log n time. For a more fun example, see Project Euler #67.
3. Even if you did rephrase "password recovery" as a decision problem and were able to show that there is not a polynomial-time algorithm for solving it, you now have to prove that "password recovery" is NP-complete.

For details on P/NP/etc. see this previous question.

Answer 6

The formal statement of this problem would be one that accepts as input the hashed value (and salt) and attempts to find a password that will generate that hash: your basic known cyphertext collision finding problem.

Depending on the quality of the hash, this might not require exponential time. Indeed, many cryptographic hashed in widespread use have identified attacks that run faster than keyspace searches.

Which is to say: you (ans some of the other responders) have assumed that the password munging routine has all the properties the designers wanted them to have. This would have to be proved.