
Re: New integer multiplication algorithm
Posted:
Mar 9, 2005 7:15 AM


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?
In any case, you learned it incorrectly. The class NP is defined *only* for decision problems. You'll see it defined that way in any standard textbook such as "Introduction to Algorithms," by Cormen, Leierson(sp?), and Rivest. or "Computers and Intractability  A Guide to the Theory of NPcompleteness," by Garey and Johnson. If you want an online source, then check section 7 of the comp.theory FAQ at http://db.uwaterloo.ca/~alopezo/compfaq/faq.html
>)> For example, the Traveling Salesman problem definately isn't a >)> problem where the answer is yes or no. >) >) But the "threshold" problem is: >) >) Input: a graph, the cost function, and a number B. >) Output: YES if there is a TSP tour with cost <= B. >) >) Now, if you have a TSP problem with integer weights, you can use the >) decision problem to find the minimum tour, using a binarysearch >) method. > > So the TSP can be turned into a decision problem. That doesn't mean > that the definition of NP includes the restriction that the problems > are decision problems. > > As an aside from that, according to the definition I gave (which you > snipped) a problem in NP can *not* be a decision problem, because it > states that a solution can be verified in P time. The solution to a > yes/no problem that is in NP can obviously not be checked in P time. > (There are only two solutions, yes and no.)
Not quite. This ignores the part of the definition about a certificate.
NP is the class of decision problems such that there is a polynomial time function f(I,c) such that for any instance of the problem, I, there is a *certificate*, c, such that f(I,c) = True if and only if the answer for instance I is yes. Also, the size of the certificate c must be polynomial in the size of the instance I.
TSP Problem (Decision Version) Input: A weighted graph G and a number W. Question: Does G have a tour of weight <= W?
Suppose we are given an yes instance of the problem. Our certificate will be the tour, i.e. the list of vertices in the order visited by the tour (note that the size of our certificate is polynomial in the size of the graph). Now we can certainly verify in polynomial time that this list of vertices is a tour whose total weight is <= W. (i.e. there is a function such that ...) Therefore, the problem is in NP.
The original and equivalent definition of NP is the following. NP is the class of decision problems that can be solved (answered) by a nondeterministic Turing machine in polynomial time. NP stands for Nondeterministic Polynomial time.
 Glenn C. Rhoads Computer Science Department Rutgers, the State University of NJ 110 Frelinghuysen Rd. Piscataway, NJ 08854

