P, NP, NP-COMPLETE, NP-HARD
The concept of P, NP, NPC, and NP-HARD are fundamental to the study of algorithms and computational complexity. The terms are used to classify problems based on how difficult they are to solve algorithmically.
P stands for "polynomial time," which means that a problem can be solved in a time that is polynomial in the size of the input. These problems are considered to be "efficiently solvable" on modern computers. Examples of P problems include sorting an array, finding the shortest path in a graph, and matrix multiplication.
NP stands for "nondeterministic polynomial time," which means that a problem can be solved in polynomial time on a non-deterministic Turing machine. These problems are considered to be "efficiently verifiable" but not necessarily "efficiently solvable" on a classical computer. Examples of NP problems include the traveling salesman problem, the knapsack problem, and the Boolean satisfiability problem (SAT).
NPC stands for "NP-complete," which is a class of problems that are in NP and are at least as hard as the hardest problems in NP. An NP-complete problem can be reduced to any other NP problem in polynomial time. The most famous NP-complete problem is the Boolean satisfiability problem.
NP-HARD stands for "NP-hard," which is a class of problems that are at least as hard as the hardest problems in NP, but may not be in NP themselves. In other words, these problems are at least as hard as the NP-complete problems, but they may not be verifiable in polynomial time. Examples of NP-hard problems include the graph coloring problem and the knapsack problem.
Polynomial reducibility is a concept used in complexity theory to compare the relative difficulty of solving problems. Two problems P and Q are said to be polynomially reducible if we can transform any instance of problem P into an instance of problem Q using a polynomial-time algorithm in such a way that the solution to the transformed instance of problem Q will give us a solution to the original instance of problem P.
In other words, if we can solve Q in polynomial time, we can solve P in polynomial time, because we can transform P into Q and then solve Q. Polynomial reducibility is often used to show that a problem is at least as hard as another problem that is already known to be difficult.
For example, if we can show that a problem P is polynomially reducible to a problem Q that is known to be NP-hard, then we know that problem P is also NP-hard, because if we could solve P in polynomial time, we could solve Q in polynomial time, which would imply that all NP problems can be solved in polynomial time, which is known to be false (unless P = NP).