Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: New integer multiplication algorithm
Replies: 26   Last Post: Mar 10, 2005 3:26 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Glenn C. Rhoads

Posts: 31
Registered: 12/13/04
Re: New integer multiplication algorithm
Posted: Mar 9, 2005 7:15 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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



Date Subject Author
2/16/05
Read New integer multiplication algorithm
Risto Lankinen
2/16/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
2/16/05
Read Re: New integer multiplication algorithm
fiziwig
2/16/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
2/17/05
Read Re: New integer multiplication algorithm
Proginoskes
2/17/05
Read Re: New integer multiplication algorithm
Oscar Lanzi III
3/3/05
Read Re: New integer multiplication algorithm
Matthew Newell
3/3/05
Read Re: New integer multiplication algorithm
Risto Lankinen
3/3/05
Read Re: New integer multiplication algorithm
Daniel A. Jimenez
3/3/05
Read Re: New integer multiplication algorithm
Dave Rusin
3/3/05
Read Re: New integer multiplication algorithm
Mike Robson
3/3/05
Read Re: New integer multiplication algorithm
Phil Carmody
3/4/05
Read Re: New integer multiplication algorithm
Matthew Russotto
3/4/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Willem
3/8/05
Read Re: New integer multiplication algorithm
Proginoskes
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/9/05
Read Re: New integer multiplication algorithm
Glenn C. Rhoads
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/9/05
Read Re: New integer multiplication algorithm
Glenn C. Rhoads
3/9/05
Read Re: New integer multiplication algorithm
Willem
3/10/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Frank J. Lhota
3/8/05
Read Re: New integer multiplication algorithm
Matthew Russotto
3/3/05
Read Re: New integer multiplication algorithm
Proginoskes
3/4/05
Read Re: New integer multiplication algorithm
Matthew Newell
3/3/05
Read Re: New integer multiplication algorithm
oberon

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.