What is missing for this P != NP proof?
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?
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.
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.
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 (ie 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, ie that P != NP.
链接地址: http://www.djcxy.com/p/39980.html上一篇: 证明暂停问题是NP
下一篇: 这个P！= NP证明缺少什么？