Why isn't NP simply "not polynomial"?

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
solution algorithm.

The class NP is defined as the set of decision problems
for which there is *nondeterministic* polynomial-time
solution algorithm.

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:

http://en.wikipedia.org/wiki/NP_%28complexity%29

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
problems?
.

Relevant Pages

  • P6 = NP (WAS: an oracle paradox)
    ... theory is the Turing machine,introduced by Alan Turing in 1936 ... solvable by some algorithm within anumber of steps bounded by some xed ... over .Then a language over is a subset L of. ... We say that R is polynomial-time i LR ...
    (sci.math)
  • P Versus NP
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • Re: Mr. P and Ms. S
    ... determine whether every language accepted by some nondeterministic ... algorithm in polynomial time is also accepted by some ... L = Lfor some Turing machine M which runs in polynomial time} The ... We say that R is polynomial-time iff L R ...
    (sci.math)
  • Re: Math errors in book Secret Life of Numbers
    ... his students have proven that primes can be found in polynomial time. ... For practical purposes the algorithm is, admittedly, still too ... that in practice, it always was solved in polynomial time using the ... the simplex method is not a polynomial-time algorithm. ...
    (sci.math.research)
  • Re: Why isnt NP simply "not polynomial"?
    ... It is the set of decision problems ... solution algorithm. ... for which there is *nondeterministic* polynomial-time ... accept the reality that "determinism" isn't really all that ...
    (comp.theory)