On Sat, 4 Nov 2000, dmolnar wrote:
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.
Actualy it's all of them. Where the question comes from is when one looks at what it different instances of a given problem (e.g. the number of closed loop paths with no double crossings of a set of bridges, or the number of sequences that a set of cities can be visited without repeats). The goal is to find a solution in a fewer number of steps. There seem to be two major categories P and NP. So for the travelling salesman problem the question becomes how to describe the way the resources and problem space grow with relation to the number of cities. Were that relation to be describable in a polynomial then it would be a P. It looks like the problem is not describable by a polynomial and is therefore NP.
It doesn't make sense to say "x^2 is in NP", strictly speaking.
Stripping context removes meaning for anything. It's also changing the rules in the middle of the game. Well, if we're going to speak strictly then you're wrong. Strictly speaking we're talking of the relative complexity to resolve certain classes of problems. And in that case it DOES make sense to word statements like this. One can say that a given problem is "x^2" (which can't be NP since x^2 is a monomial, a class of polynomial and therefore P) with relation to resources or number of potential solutions with respect to going from n to n+1. So, if I have 10 of something and manipulate them and it takes me x amount of time and y resources. And I know the problem is "x^2" then I know that even small changes will drasticaly increase the number of solutions that I have to resolve. In fact I know that if I go to 20 of them things then I'll have to deal with a run time of approx. x^2 and require about y^2 resources. The point is to find an algorithm that uses those resources more sparingly.
It doesn't make sense to say "Ford-Fulkerson is in NP", strictly speaking.
It depends on it's complexity. And it does make sense of speaking to a particular algorithm (e.g. Seive of Aritoshanese) as being NP (which it is).
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?"
No, because 'primality testing' has a host of algorithms. It appears they are NP, but if somebody were to find a NEW algorithm that did it in P then primality testing, at least with respect to that algorithm, would be a P class problem. Another aspect of the N=NP is that the assumption is that if we can resolve a single NP to a P then that should resolve ALL NP to P. That's a pretty big leap with no real analysis behind it. A canon of faith rather than proof or fact. So the question does in fact effect isues of problem class, algorithm selection, and execution resource requirement. ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------