Terms like "P, NP" should not be unfamiliar to computer science or software engineering major student, and in fact you might have already heard it thousands of times. However, when asked about what is the real definition of these terms, when and where to use them exactly, many people may shake their head.
First of all, "P, NP, co-NP, PSPACE" can be only used to describe decision problems. A decision problem is a question with a yes-or-no answer given some input parameters. For instance, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem.
On the other hand, it is not correct to say that the knapsack problem (a optimization problem) is in NP, but it is right to say that the decision version of knapsack problem is in NP. (Don't worry about what is in NP right now).
Secondly, the algorithm (solution to the decision problem) we are talking about is under Turing Machine model, so it is necessary to know what kind of Turing Machine we are talking about. According to Wikipedia: 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, by contrast, may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left" and "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set.
In other words, the computer we are use every day is deterministic Turing Machine. Suppose you write a program to figure out how many prime is smaller than 10, in a deterministic Turing Machine, you need iterate from 1 to 10 sequentially. In a non-deterministic Turing Machine, however, you can check 1 to 10 simultaneously, i.e., you could think of non-deterministic Turing Machine as a supercomputer with infinite parallel computing power. Note that non-deterministic Turing Machine is a theoretical product, there is no such thing in real world. The idea to introduce non-deterministic Turing Machine is to describe how hard certain problem is, say if I give you such computing power, then you can solve these kind of problems in polynomial time, but in fact you don't have, so right now we don't know how to solve those problems efficiently.
P (Polynomial) is one of the most fundamental complexity classes. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
Definition: A language L is in P if and only if there exists a deterministic Turing machine M, such that
Recall the decision problem above: "given two numbers x and y, does x evenly divide y?". Obviously, this problem is in P because we can solve it in polynomial time.
NP stands for "Nondeterministic Polynomial", not "not polynomial". A problem is in NP if and only if there exists a polynomial time verifier for a proposed answer to the problem.
Note that $P\in{NP}$, because we can simply use the algorithm of solving it to verify it in polynomial time.
One example is the vertex cover problem: Given a graph, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Does there exist a vertex cover with size of $B$ (some boundary).
There is no known efficient polynomial algorithm to solve this problem exactly, but we are able to verify whether a proposed answer (like each step in brute force method) is correct in polynomial time.
A decision problem $X$ is NP-Complete if and only if 1) $X$ is in NP 2) Every problem $Y$ in NP can be reduce to $X$ in polynomial time, i.e. $Y\leq_{p}X$.
NP-Completeness problems are viewed as the hardest problems in NP.
The hardest part is to prove the first NP-Completeness problem, because one need to show that every problem in NP can be reduce to it in polynomial time. Fortunately, some really smart guy already did this for us, they proved that "Boolean satisfiability problem" (i.e. SAT) is NP-Complete.
Therefore, now if we want to prove some decision problem $X$ is NP-Complete, we only need to show two things. 1) $X$ is in NP. 2) $SAT\leq_{p}X$.
There is a very nice property of NP-Completeness problem, that is, if we can solve one of them in polynomial time, then we can solve all of them in polynomial time simply by first reduce other problems to that problem we can solve, then use the solver to solve it in polynomial time.
Since every problem in NP can be reduce to that problem, we can solve every problem in NP in polynomial time, i.e. $P=NP$.
Note that though the majority of people think that $P\neq{NP}$, it is still an open question because no one can prove $P=NP$ or $P\neq{NP}$ so far.
Sometimes a decision problem is hard to see whether it is in NP or not, we are certain that its complementary problem is in NP. Then we call the problem is in co-NP if and only if its complementary problem is in NP.
An example of an NP-complete problem is the subset sum problem: given a finite set of integers, is there a non-empty subset that sums to zero? To give a proof of a "yes" instance, one must specify a non-empty subset that does sum to zero. The complementary problem is in co-NP and asks: "given a finite set of integers, does every non-empty subset have a non-zero sum?" This problem is not obviously seen to be in NP.
By far we only consider the time complexity of algorithms, now we are going to talk about the space complexity.
PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
A decision problem is PSPACE-Complete if and only if 1) it can be solved using a polynomial amount of space 2) Every problem in PSPACE can be reduce to it in polynomial time (polynomial reduction).
For example, given a regular expression R, determining whether it generates every string over its alphabet is PSPACE-complete.
Not all the problems can be transform to a decision version, and NP-Hard is to describe optimization problem while other terms mentioned above is to describe decision problem.
Acknowledgement:
This article is my learning notes of course CS331 Algorithms and Complexity (Spring 2014), lectured by Prof. Greg Plaxton.