Willem wrote: > email@example.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.