# Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development
## 2 Materials and Methods
### Combinatorial Optimization Problem Classification System
#### 2.3.8 Problem's Computational Complexity  
The search space, which is the set of admissible solutions for an optimization problem, is usually exponential with respect to the size of the input. This happens for the vast majority of the real-world combinatorial problems [35]. In particular, the size of the input is determined according to the specific problem. For instance, solving an instance of the minimum spanning tree problem requires in input a weighted graph, and the input size corresponds to the number of nodes and edges of such a graph. This example suggests that different instances of the same optimization problem are characterized by a different size of the input. As a consequence, it is not possible, for non-trivial problems, to define an algorithm that provides an optimal solution for all the possible problem instances within a time constraint that is polynomial in the input size [52]. For this reason, it is fundamental to take into account the time needed by an algorithm to provide the final solution. The time also depends on the hardware available, and the same algorithm executed on the same instance, but different computers may provide significantly different running times. For this reason, to perform a fair comparison, it is common to consider a different concept that is the computational complexity of an algorithm. The computational complexity allows calculating the time an algorithm needs to return the final answer or solution as a function of the input size. Thus, computational complexity is the commonly used method for comparing the running time of two different algorithms because it is independent of the hardware on which the algorithms are executed. Computational complexity considers the number of basic operations to be performed during the execution of the algorithm and uses this information to provide an indication of the running time as a function of the input size. For instance, an algorithm that must visit all the vertices V of a graph given in input has a complexity of O(V). In other words, its complexity is linear with respect to the input size (i.e., the number of nodes of the graph). To distinguish between easy and difficult decision problems, one should consider the class of problems that are solvable by a deterministic Turing machine in polynomial time and problems that are solvable by a nondeterministic Turing machine in polynomial time. Without going into formal detail related to the Turing machines, it is possible to provide an intuitive definition of the two classes of problems, which are known as (1) P and (2) NP [35]. In particular, a decision problem is in P if and only if it can be solved by an algorithm in polynomial time. On the other hand, a problem is called NP (nondeterministic polynomial) if its solution can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess. Thus, the algorithm used to solve a problem in NP consists of two steps. The first consists of a guess (generated in a nondeterministic way) about the solution, while the second step consists of a deterministic algorithm that verifies if the guess is a solution to the problem [48; 53]. Finally, if a problem is NP and all other NP problems are polynomial-time reducible to it, the problem is NP-complete. In other terms, determining an efficient algorithm for any NP-complete problem implies that an efficient algorithm can be found for all the NP problems.  
This distinction is important in the context of metaheuristics: problems that are in NP are commonly addressed using metaheuristics. In this case, the algorithms run in polynomial time and provide a solution that approximates the optimal one.