On Sat, 4 Nov 2000, Jim Choate wrote:
On Sat, 4 Nov 2000, Declan McCullagh wrote:
"NP" problems, on the other hand, are those that can be solved in nondeterministic polynomial time (think only by guessing). NP includes P.
Actualy any time that can't be described using a polynomial (i.e. a0 + a1x + a2x^2 + ...) is NP. For example something that executes in factorial or exponential time is NP.
I'm sorry - by the definitions I know, Declan has it closer. I'm not sure what you're getting at with "any time that can't be described..." or "something that executes in factorial or exponential time." As far as I know, NP is a class of *problems*, not a class of running times or even a class of algorithms. It doesn't make sense to say "x^2 is in NP", strictly speaking. It doesn't make sense to say "Ford-Fulkerson is in NP", strictly speaking. It makes more sense to say "primality testing" is in NP, if that refers to the problem of "Given a number n, is n prime?" NP can be defined as the class of problems for which there exist "succint certificates". That is, given a problem instance, there is some string S which a) is "succint" - its size is bounded by some polynomial in the size of the problem instance, b) can be verified as a "real" solution to the problem in polynomial time. i.e. the solution has a "certificate" which will convince you beyond doubt that this really is a solution. By the way, I don't recall if anyone's defined polynomial time yet in this thread. "Polynomial time" means that a computer will take a number of "steps" bounded by some polynomial which takes as parameter the length of the problem instance. Here "steps" mean what you think they mean; pinning them down precisely requires specifying your model of computation precisely, which can be time-consuming. NP is the class of all problems for which these "succint certificates" exist. Once you've found an answer, you can check it easily. But you are *not* guaranteed anything about finding the answer. Finding the answer might be "hard." This is one way of thinking about NP. Declan seems to have in mind an alternative (but equivalent) definition, in which we consider NP as the class of problems solvable by machines which have the magic ability to always know the "right" way to go at every branch point of a computation. This is another way to think about it; I personally prefer the "succint certificate" definition. Then P is the subset of NP -- problems for which finding the certificate is "easy." That is, there is a polynomial-time algorithm for finding a solution to the problem in the form of one of these "succint certificates." The P vs NP question is then whether P is a proper subset - i.e. is there some problem in NP but not in P? Factoring in in NP. A succint certificate that you've factored a number n are its factors, because you can just multiply them together to check. Finding the factors is another thing entirely... There are many more isssues here, of course. One such issue is the average case hardness of a problem. In the case of RSA, we actually have that RSA is "randomly self-reducible" -- the ability to solve even a small fraction of instances (say 1%) of all RSA instances would imply the ability to solve every RSA instance. This gives some evidence that RSA is "uniformly hard." But this is not known for many other problems in NP, for which the average case complexity is unclear. More fun on that subject may be found at Russell Impagliazzo's page http://www-cse.ucsd.edu/users/russell/ in the paper "A Personal View of Average Case Complexity." -David