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

If you show that any algorithm that solves "password recovery" requires more than polynomial time, then it does demonstrate that P ≠ NP.

Otherwise, if you only show that one particular solution requires more than polynomial time, it demonstrates nothing. I can write a sort to require exponential time (shuffle array until it's sorted), but that doesn't mean there's no polynomial solution.

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.