Re: New integer multiplication algorithm

gcrhoads_at_yahoo.com
Date: 03/09/05 

Date: 9 Mar 2005 04:15:32 -0800

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

Relevant Pages

  • Re: A variant of Traveling Salesman Problem
    ... > tour exist", in polynomial time, in the general case, ... Why each iteration is polynomial? ... but we still don't know how to find that shorter tour in polynomial ...
    (comp.theory)
  • Re: NP, P and the problem of finding a proof
    ... deterministic Turing machine which accepts a 'corresponding' language ... (does there exist a tour having total length <= L?), ... you can check in polynomial time whether it is a ... linear integer programming with a given set of linear constraints and ...
    (sci.math)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... polynomial time the question "does this TSP instance have a tour of ... TSP instance have a tour of cost <= C?"? ... The transformation of an arbitrary TSP into a TSP with a unique optimal ... in which Hofman says that we can convert this single ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... confessed that our Transformation does not answer the decision-version ... does there exist a tour of length < C) ... answers" or "1 answers" as a tag to the problem, in polynomial time by ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... can be identified within polynomial time. ... Hmmm, ... add to each weight number something like that random ... algorithm giving correct answer for TSP having one optimal solution then ...
    (comp.theory)