The problems of operational research, and more generally of the decision making, are often Np-complete, that is to say that we do not know any algorithms allowing to find an optimal solution in polynomial time, but we know how to obtain a feasible solution in polynomial time.
An algorithmhave a polynomial complexity if there exists a polynom P such that the number of elementary instructions carried out during its execution on an instance of size n is at most P(n). A problem have a polynomial complexity if there is an algorithm of polynomial complexity solving it. It is important to emphasize that the representation of the data structures used does not affect complexity.
A decision problem P is reduced to a decision problem P’ if there exists a polynomial algorithm R that transforms any input u of P into an input u’ = R(u) of P’ such that u∈YES(P) ⇔ u’∈YES(P’).
This suggests the following implication: if there is a polynomial algorithm for P’, then there is also one for P.