The class of all languages which can be recognised by a nondeterminstic Turing machine (which see!) in polynomial running time. Clearly this class includes all problems in P. It seems very clear that it should contain problems which are not in P, but unfortunately this is not known (and is very much an open problem). Symbolically, we know that
P ⊆ NP
;
the question is if
P = NP
.
Briefly put (but you should still read the node!), a "nondeterministic" Turing machine is a Turing machine with an extra tape. The extra tape is initially filled with arbitrary bits. The machine "accepts" a word w if there is some initial configuration of the arbitrary bits on the extra tape for which the machine halts with output "1" on its main tape. Note that we have no known source which will supply us with these arbitrary bits!
Since a Turing machine running in polynomial time will require the use of only polynomially many nondeterministic bits, we can prespecify the "correct" bits for a successful computation for any element of a language in NP. So an alternative definition of NP is the set of all languages L for which a function f(x,y) exists, which is in P, and such that x is in L iff there exists a y, with |y| polynomial in |x|, for which f(x,y)=1.
Many complete problems are known for NP. Among them are SAT, 3-SAT, hamiltonian path, chromatic number, and integer linear programming. See NP-complete for further discussion of this "tip" of the NP iceberg.
Note on a misconception appearing below:
It is NOT true to say that the class NP consists of all problem solvable in exponential time on a deterministic Turing machine. While it is true that
NP ⊆ ∪c≥1 DTIME(2nc)
i.e., any problem in NP can be solved in exponential time, the converse is
not known to be true! (Sketch of a proof why the inclusion holds: Run the NDTM on
every possible initial configuration of arbitrary bits; accept if even one initial configuration finds a solution. If the machine runs in time O(n
c), this requires us to scan O(2
nc) different configurations for total deterministic running time O(n
c⋅2
nc) = O(2
nc)).
Note also that "exponential time" actually means more than just time O(2n); this is another one of the oddities of notation in computational complexity.
Similarly, there are other "magic" ways to use arbitrary bits which yield different complexity classes. co-NP is one example. A more interesting example is the problem of solving all games of perfect information and polynomial length for which legal moves and victory can be determined in polynomial time. This problem is not known to be in NP; however it is a complete problem for PTIME, and can be solved in not much more than "exponential" time.