Willem
Posts:
145
Registered:
12/10/04


Re: New integer multiplication algorithm
Posted:
Mar 4, 2005 4:08 PM


Proginoskes wrote: ) You're comparing apples with oranges here. NP problems are problems ) where the answer is YES or NO (only one bit long).
I'm pretty sure you're wrong there. For example, the Traveling Salesman problem definately isn't a problem where the answer is yes or no.
You may be confused in that NP problems are such that a solution can be checked to be correct in polynomial time. To be more precise: NP is Nondeterministic Polynomial. Nondeterministic means that the algorithm can 'choose' multiple paths at certain points (I.E. it is not determined what the outcome is). This means that actually the NP algorithm is: 'guess a solution, and check if it's correct.' And the fun bit about nondeterministic machines is that they will 'guess' the solution that makes it run successfully. (As you may have guessed, those don't actually exist.)
To make a nondeterministic machine deterministic, you simply iterate through all possible choices until you get a successful one. This usually takes exponential time.
(I hope I explained that in a somewhat understandable manner, and still managed to not make a silly mistake somewhere.)
SaSW, Willem  Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT

