In general, we say an algorithm is efficient if it is O(nk) for some constant, k, and this is called a polynomial algorithm.
Given a problem in which there is a polynomial algorithm even for the worst case, the algorithm is denoted by P (polynomial).
There is another set of algorithms called NP (nondeterministic polynomial). An NP problem is a problem for which the solution can be verified in a polynomial time.
If a problem, P, has an algorithm that runs in a polynomial time, we can also verify its solution in polynomial time. Then, we can conclude that P is a subset of, or equal to, NP. However, it is unknown whether P = NP.
NP-complete problems are the hardest problems in an NP set. A decision ...
