|
|
Re: New integer multiplication algorithm
Posted:
Mar 9, 2005 3:31 PM
|
|
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.
|
|
