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 ]
Glenn C. Rhoads

Posts: 31
Registered: 12/13/04
Re: New integer multiplication algorithm
Posted: Mar 9, 2005 3:31 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Willem wrote:
> gcrhoads@yahoo.com wrote:
>) Willem wrote:
>)> Proginoskes wrote:
>)>) Not according to Papadimitriou's _Computational Complexity_.
>) Problems
>)>) in NP are decision (YES/NO) problems.
>)>
>)> Well then either your source is simply different from mine, or you
>)> read 'are' where it sais 'can be turned into', or 'are equivalent
>) to'.
>)> In any case, see below for why decision problems can't be NP
>) problems,
>)> according to the definitions I was taught and can find on the Web.
>)
>) What is your source?
>
> I don't recall what the book was called, but this is my web source:
>
> http://mathworld.wolfram.com/Complexity Theory.html


It does neglect to mention that it is defined in terms of
decision problems. The author of this site, Eric Weisstein,
is an astronomer not a mathematician (astronomer's do use a
lot of math though).

>) <snip definition of NP, which I accept>
>
> Well, to me it sounds a bit like a different way of notation.
> You need the non-decision solution to check in P time, but you
> don't actually call it the solution, you call it a certificate.


That depends on what you mean by the solution; the certificate
does not necessarily correspond to the optimal solution. Consider
the decision version of TSP, for example. Suppose the instance is
some weighted graph and the value 100. Further suppose that the
weight of the minimum tour is 50. The certificate could correspond
to a tour of weight 80, 90, or anything <= 100.


> And in the site you mentioned, they even say that it's
> only a way to make theorizing easier.


That's the motivation for restricting the definition to decision
problems. Note that if you can solve the decision problem in
polynomial time, then you can generally solve the corresponding
optimization problem in polynomial time.


> ) The original and equivalent definition of NP is the following.
> ) NP is the class of decision problems that can be solved (answered)
> ) by a non-deterministic Turing machine in polynomial time.
> ) NP stands for Non-deterministic Polynomial time.
>
> That's the definition I was taught. I infer that this is an older
> definition, and that the decision-problem one is the newer one ?
> Would you happen to know when this change in definition was accepted

?

Yes, this is an older definition but note that it too deals
only with decision problems. The two definitions are
mathematically equivalent. People started using the newer
one for didactic reasons. With the newer definition, you
can teach NP-completeness without requiring someone to first
take a course in Automata Theory and Formal Languages. You
don't even have to explain non-determinism (unless you want
to).

I don't know who came up with the newer definition or when.
The earliest textbook I can think of that uses it is the
second edition of the Sara Baase text from 1988 but there
may be an earlier text.


As an aside, I definitely prefer the second edition of this
text to the newer third edition by Baase and Van Gelder. The
only good thing about the newer edition is the expanded coverage
of graph algorithms. The bad part is everything else. The
exposition is consistently worse than in the older 2nd edition.
The authors should have followed the advice, if it ain't broke,
don't fix it.



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.