Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: New integer multiplication algorithm
Replies: 26   Last Post: Mar 10, 2005 3:26 PM

 Messages: [ Previous | Next ]
 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

Date Subject Author
2/16/05 Risto Lankinen
2/16/05 Oscar Lanzi III
2/16/05 fiziwig
2/16/05 Oscar Lanzi III
2/17/05 Proginoskes
2/17/05 Oscar Lanzi III
3/3/05 Matthew Newell
3/3/05 Risto Lankinen
3/3/05 Daniel A. Jimenez
3/3/05 Dave Rusin
3/3/05 Mike Robson
3/3/05 Phil Carmody
3/4/05 Matthew Russotto
3/4/05 Proginoskes
3/4/05 Willem
3/8/05 Proginoskes
3/9/05 Willem