Why isn't NP simply "not polynomial"?
- From: Digital Puer <digital_puer@xxxxxxxxxxx>
- Date: Sun, 25 Nov 2007 20:57:28 -0800 (PST)
I'm taking an upper-division class in algorithms and
have some questions that my instructor wasn't able
to answer for me clearly (or more accurately, that
I wasn't able to fathom).
I understand the class P: It is the set of decision problems
for which there is a deterministic, polynomial-time
The class NP is defined as the set of decision problems
for which there is *nondeterministic* polynomial-time
So here are my questions:
Why do we have to bring in non-determinism at all?
Why can't NP be defined as the class of decision problems
for which the best (known) solution is a *deterministic*
superpolynomial solution algorithm?
For instance, the subset-sum problem is pretty
obvious to me: the running time to solve it has to
run in O(2^N) time, which is super-polynomial.
Since it is "not polynomial" it can't be in P and
must be in NP.
Final question: Just looking at the venn diagram on the
wikipedia article on NP completeness:
Why kind of problems fall into NP but are not in P
and are not in NPC, assuming P != NP? For these
problems in NP, am I correct in assuming that other
problems in NP cannot be reduced to these
- Prev by Date: Errata for Semigroups and Combinatorial Applications by G. Lallement?
- Next by Date: Re: Why isn't NP simply "not polynomial"?
- Previous by thread: Errata for Semigroups and Combinatorial Applications by G. Lallement?
- Next by thread: Re: Why isn't NP simply "not polynomial"?