|
|
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 NP-completeness," by Garey and Johnson.
If you want an online source, then check section 7 of the comp.theory
FAQ at http://db.uwaterloo.ca/~alopez-o/comp-faq/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 binary-search
>) 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 non-deterministic Turing machine in polynomial time.
NP stands for Non-deterministic Polynomial time.
--
Glenn C. Rhoads
Computer Science Department
Rutgers, the State University of NJ
110 Frelinghuysen Rd.
Piscataway, NJ 08854
|
|
