Hi Bill, On Sat, 4 Nov 2000, Bill Stewart wrote:
Jim, you're misunderstanding the class NP, though you're correct in not holding your breath.
It's not "all problems that can't be solved in polynomial time." It's "all problems that can be solved in polynomial time by a non-deterministic Turing machine." A non-deterministic Turing machine is allowed to guess answers (or at least, to guess a polynomial number of answers). Answers to NP problems can be verified in polynomial time - the hypothetical machine guesses the answer, and verifies it in a polynomially bounded time.
Which is mathematicaly equivalent to having an algorithm that solves the problem directly in polynomial time. One only has to add to the solution time the factor that represents the 'walk time'. Let's consider a prime seive. The numbers are the positive integers and they're a line. So we take the time to check the solution for any given guess and add to it an 'mx+b' factor to represent the time to generate your guesses (in this cases the positive integers). Last time I checked a polynomial plus a polynomial was just another polynomial. We're not talking about absolute magnitudes but rather the relative magnitude differences of the algorithms. How one pronounces 'tomato' isn't relevant. In fact, it is clear that if the algorithm necessary to generate your 'guess' is itself non-polynomial then you've demonstrated the sum (i.e. time to generate guess plus time to check) can't itself be polynomial. In the case where a random number is used to generate a guess then the factor is a simple constant (i.e. '+c') added to the solution time. Iterations by constant value will also consist of the 'loop time' to execute the sum, again a simple constant. So, in most cases the effort needed to generate the guess or walk sequentaly through a state space or through a random proceess is inconsequencial. ____________________________________________________________________ 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 --'- --------------------------------------------------------------------