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?

Malamut

I have discovered a truly remarkable proof which this margin is too small to contain – Priapism

Answer 1

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.

Stouthearted

Brute force password recovery is by all means a computational problem. It's easily reducible to a valid input into standard Turing machine. Such reductions are basis for a substantial part of entire computer science. – Quesenberry

Answer 2

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.

Valuator

No, you also have to rephrase "password recovery" as a decision problem and show that the rephrased problem is NP-complete. – Faison

But how else could the problem of cracking an arbitrary password solved as by an brute force which requires exponential time? Isn't it the heart of the problem that the solution (e.g. password) must be known otherwise you would have to search the whole solution space? – Malamut

@gruenewa: The goal is to make it hard (i.e. to make password encryption easy and decryption hard). But the proof that your algorithm behaves in this way (as in: decryption cannot be computed in polynomial time on a deterministic machine) has never been done. – Arak

Answer 3

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.

Lincolnlincolnshire

Answer 4

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.

Arak

Jason comment about "password recovery" not being a decision problem is right. However, in practice, this is often not an issue, as there are practical "tricks" for turning decision problems from/into free-answer problems. For example, instead of "password recovery" you could ask the system: "is the password above MMMMMMMM or below?". – Arak

You don't have to show that it is NP-complete. It is sufficient to prove a lower bound on the complexity for any problem in NP, not just the complete ones, to separate the two classes and show that P!=NP. – Bess

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.

Faison

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.

Fearsome

Answer 7

Writing this answer because I had this idea at some point, and the answers here were not satisfactory.

You have proved that P =/= NP under the presence of an 'Oracle' (this is the thing that tells if the password is right or not).

It has been shown you can actually not prove the original P vs NP by using Oracles (this technique is called relativisation).

In order to prove the original problem you have to define the Oracle in terms of a turing machine. In other words, you have to describe what the password verifier does with the input, and then prove that there is no algorithm that can guess the password given the password verifier code.

Note that you have to do this for any possible fast password verifier. The only requirement of the password verifier algorithm is that it runs in polinomial time with regards to the password length.

So given any possible algorithm that checks if the password is right or not in polinomial time, you have to write an algorithm that reads the verifier algorithm and tries to guess the password is in polinomial time. If you can prove or disprove that such algorithm exists then you have solved the problem.

Piton