http://en.wikipedia.org/wiki/P_versus_NP_problem
http://en.wikipedia.org/wiki/Sharp-P
http://en.wikipedia.org/wiki/Sharp-P-complete
the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input;
the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.
NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time, and whose solution may still be verified in polynomial time.
NP-hard problems are those at least as hard as NP problems, i.e., all NP problems can be reduced (in polynomial time) to them.NP-hard problems need not be in NP, i.e., they need not have solutions verifiable in polynomial time.
#P is the class of function problems of the form “compute ƒ(x)”, where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time.
#P problems ask “how many” rather than “are there any”.
a problem is #P-complete if and only if it is in #P, and for any non-deterministic Turing machine, the problem of computing its number of accepting paths can be reduced to this problem.
In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation.
A non-deterministic Turing machine (NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation.
ShareOnSite 