COP's are interesting because they include both the easiest and hardest problems to solve. The difference is described by the partition of all optimization problems into two sets, P and NP-Complete. The classification of problems into these two sets and by other distinctions is the subject of complexity theory and is far beyond this simple introduction. The subject is important to OR practice, however, because a particular problem will probably be tractable if it is identified as a member of P, while the problem will probably be difficult or impossible to solve if it is identified as a member of NP-Complete.

A problem in the set P can be solved by an algorithm whose solution time grows as a polynomial function of the size of the problem. For example the shortest path problem for a network with having n nodes and with non-negative arc lengths can be solved with Dijkstra's algorithm. If implemented correctly, the computation time is bounded from above by a constant times the number of nodes squared. We say the solution time is order or . Since the function in the parentheses is a polynomial, this is a polynomial algorithm and the shortest path problem with positive arc lengths is in the set P. We say that this is an easy problem because large problems can be solved in reasonable times with the proper algorithm and on a fast computer. A variety of special case COP's fall in the set P including versions of the assignment, minimal spanning tree, shortest path tree, pure network flow programming and linear programming problems.

For the problems in the set NP-Complete, no polynomial algorithms have been found. As an example, the time for enumerating all the solutions of a binary IP with n variables is . The function in the parentheses is exponential in n. This is bad news. Although it may be possible to solve problems by enumeration for some small n, it is clear that for some larger n the enumeration will be impossible. One might ask, "why not solve the problem with a more efficient method such as branch and bound or with cutting planes?" The answer is that these methods also have exponential bounds. In fact, no polynomial algorithm has been found for the binary IP problem. If one could find one, the problem would be in class P. In fact, most researchers would say that it is unlikely that such an algorithm will ever be discovered. Again, one might ask, why not wait for a faster computer to be invented? Surely there will be one. The answer is that no matter how fast computers become, exponential growth will eventually make problems of some size unsolvable. On the following pages we call problems in the NP-Complete class hard problems.

What does this say to someone who must solve a COP? If the problem can be reduced to a member of the class P, just apply the associated the algorithm. Even if a problem is in P it may not be easy to solve because appropriate algorithms are not always easy to find, easy to program or inexpensive to purchase. For a given COP it is often not easy to tell if it can or cannot be reduced to P. Even if the COP is identified as a member of P, a slight variation of the problem, perhaps a change in form for the objective function or the addition of a constraint, may cause the COP to be no longer reducible to P. It is easy to find the shortest path from node a to node b in network, but if the path is required to have at least a specified number of arcs, the problem becomes hard.

If the problem cannot be reduced to a problem in P, does that mean it is in the class NP-Complete? We can prove that a problem is in NP-Complete if we can take some problem that is known to be NP-Complete and reduce it to the problem at hand. Again, this is not always easy to determine.

If the analyst is not able to classify a problem, if it cannot be reduced to a member of P or one does not have a convenient algorithm, is all lost? The answer is that a problem can be solved to optimality if it is not too big. If it is too big, then there are heuristic methods that may yield acceptable solutions.