First Tim wrote:
Factoring is suspected to be in the class NP (or even harder, some suspect), but it has not yet been proved to be so.
NP is nondeterministic polynomial time, meaning that you can verify the answer in polynomial time. You need not be able to derive the answer in P time. The 'nondeterministic' part means that the machine guesses the reason for the correct answer and then verifies that it has the right answer. The reasoning is encoded in a piece of data called a witness. Since one can multiply two numbers together quickly, factoring is NP-hard. (X-hard means that the answer comes from a 'short' sequence of decision questions in complexity class X.) The verification, multiplication, is in P, so factoring, the inverse of multiplication, is NP-hard. Since every P problem can be verified in P time (by running the P time algorithm without the need for a witness), P is a subset of NP. The unknown question is whether it is a proper subset. Then James wrote: Those who have studied the matter generally believe that factoring is NP, but is not NP complete. Factoring isn't in NP. Factoring is NP-hard. Problems in P and NP are decision problems, i.e. problems which have true or false answers. NP-hard means that the problem can be reduced to answering a short list of NP problems. In this case, those questions might be "Is the second-lowest bit of the smallest factor a 1?" and so on, questions about specific properties of the factorization. Note that a factorization makes a suitable witness for every such NP question. Factoring cannot be "even harder than NP" since a simple minded brute force attack is 2^(n/2), which is only NP 2^n problems give you E, exponential time. There's also NE, nondetermistic exponential time, problems which have witnesses verifiable in E time. Merely having an exponential time algorithm does not mean that the problem is in NP. NP is a subset of E, however. The easy algorithm is exhaustive search of the space of possible witnesses, which in exponential in the length of the P time verification method, and therefore exponential in the length of the input. As Timothy May points out, if factoring is NP, then modest increases in key length can easily defeat enormous improvements in factoring. Also not quite true. Consider a putative problem whose provably best algorithm is O(n^(log log n)). This algorithm dominates every polynomial (and hence is _not_ in P), but grows extremely slowly. How extremely? Take the log base at 10 and n = 1 googol. The calculation yields O(n^2). No such algorithms or problems are known, I might add; neither is their existence firmly denied. Eric