Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Willem

Posts: 145
Registered: 12/10/04
Re: New integer multiplication algorithm
Posted: Mar 4, 2005 4:08 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
Read New integer multiplication algorithm
Risto Lankinen
2/16/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
2/16/05
Read Re: New integer multiplication algorithm
fiziwig
2/16/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
2/17/05
Read Re: New integer multiplication algorithm
Proginoskes
2/17/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
3/3/05
Read Re: New integer multiplication algorithm
Matthew Newell
3/3/05
Read Re: New integer multiplication algorithm
Risto Lankinen
3/3/05
Read Re: New integer multiplication algorithm
Daniel A. Jimenez
3/3/05
Read Re: New integer multiplication algorithm
Dave Rusin
3/3/05
Read Re: New integer multiplication algorithm
Mike Robson
3/3/05
Read Re: New integer multiplication algorithm
Phil Carmody
3/4/05
Read Re: New integer multiplication algorithm
Matthew Russotto
3/4/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Willem
3/8/05
Read Re: New integer multiplication algorithm
Proginoskes
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/9/05
Read Re: New integer multiplication algorithm
Glenn C. Rhoads
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/9/05
Read Re: New integer multiplication algorithm
Glenn C. Rhoads
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/10/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Frank J. Lhota
3/8/05
Read Re: New integer multiplication algorithm
Matthew Russotto
3/3/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Matthew Newell
3/3/05
Read Re: New integer multiplication algorithm
oberon

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.