1.1 Problems and Complexity
When solving problems, it can be observed that not all of them present the same degree of difficulty. Thus, given any problem, how is determined whether it is easy of difficult? Or even more so, what does it mean a problem is easy or difficult? This subject is treated by a brach of mathematics called algorithmic complexity. Algorithmic complexity establishes a classification of the different types of problems by their degree of difficulty according to the computational complexity of the simplest algorithm that ensures their resolution. The problems can be classified into two large groups:
- •
Intractable problems: include those that are formally undecidable (Minsky, 1967), there is a demonstrationthat there is no algorithm that allows to solve them in all cases. Intractable problems also include all those problems for which an algorithm is known that could solve them, but for which the amount of computational time required to this, makes them inaccessible even for “reasonable” sizes. This is independent of the computational capacity available. It can formally be said that there is no algorithm that allows solving it in a series of steps that is a polynomial function of the input size of the problem.
- •
Treatable problems: these are problems of class P that can always be solved using an algorithm that involves several steps that is a polynomial function of the input size of the problem.
In summary, it can be said that problems of class P can be solved in polynomial time and intractable ones cannot be solved in polynomial time.
Additionally, an extra classification can be established for those decidable but intractable problems, for which there is at least the possibility of calculating, in a number of steps that is a polynomial function of the size of the problem, if a solution belongs to its solutions. These problems together with those of class P form class NP.
Problems of the class NP are those that can be solved using an imaginary machine called a Non-Deterministic Turing Machine (NDTM), in several polynomial steps. Many of the problems in the NP class are quite common problems, appearing regularly in different areas of engineering and include, but are not limited to, set partitioning problems, network design, planning, optimization, information retrieval, etc. (Garey & Johnson, 1979).
Of all the problems of the NP class, a set of them called NP-complete can be distinguished, which are the most difficult to solve. Cook's Theorem (Cook, 1971) allows us to determine whether a given NP problem belongs to the NP-complete class. The property of the NP-complete class is that every problem of the NP class can be polynomially transformed into it.
However, optimization problems are not generally found in the NP class and therefore may not be NP-complete. Therefore, in general, it is not possible to check whether an optimal solution has been achieved in several steps that is a polynomial function of the size of the problem. In most cases it is only possible to verify this by comparing it with the entire set of solutions to the problem. If the set of solutions grows exponentially with the size of the problem, it is evident that the verification cannot be carried out in polynomial time. These optimization problems are in a class of problems called NP-hard.
From all that has been said above, it is indisputable that for NP-hard optimization problems there is no algorithm in polynomial time that allows determining the optimal solution to the problem. For this reason, approximate methods are used by means of heuristics that allow us to approach an optimal solution generating feasible solutions to the problem that are of practical use.