III. Search Space
Search Space
When we solve a problem, we are usually looking for a solution that is the best among all possible candidates. The set of all feasible solutions (that is, the set of objects among which the desired solution lies) is called the search space (also called the state space). Each point in the search space represents one feasible solution. Each feasible solution can be "marked" by its value or fitness for the problem. Our goal is to find the solution, which corresponds to one or more points in the search space.
Looking for a solution is therefore equivalent to searching for some extreme (a minimum or maximum) in the search space. The entire search space may be known at the time the problem is being solved, but more often we know only a few points and generate additional ones as the search continues.
Example of a search space
The problem is that this search can be very complicated. It is often unclear where to start or where to look for the solution. There are many methods for finding a suitable solution (that is, not necessarily the best solution), such as hill climbing, tabu search, simulated annealing, and the genetic algorithm. The solution found by these methods is often considered a good one, because it is frequently impossible to prove what the true optimum is.
NP-hard Problems
Examples of difficult problems that cannot be solved in a "traditional" way are NP problems.
There are many tasks for which we know fast (polynomial) algorithms. There are also some problems that cannot be solved algorithmically in polynomial time. For some problems, it has been proved that no polynomial-time solution exists.
But there are many important tasks, for which it is very difficult to find a solution, but once we have it, it is easy to check the solution. This fact led to the class of NP-complete problems. NP stands for nondeterministic polynomial, which means that it is possible to "guess" a solution (using some nondeterministic algorithm) and then verify it, both in polynomial time. If we had a machine that could guess, we would be able to find a solution in some reasonable time.
For simplicity, the study of NP-complete problems is usually restricted to problems where the answer can be only yes or no. Because there are also tasks with more complicated outputs, the class of NP-hard problems was introduced. This class is broader than the class of NP-complete problems.
NP problems are often characterized by the fact that a simple algorithm for finding a solution is obvious at first sight: just try all possible solutions. But this algorithm is very slow (often O(2^n)), and even for slightly larger instances of the problem it becomes completely impractical.
Today nobody knows if some faster exact algorithm exists. Proving or disproving this remains a major challenge for researchers (and maybe for you! 😊). Today many people think that such an algorithm does not exist, and so they are looking for alternative methods - genetic algorithms.
Examples of NP problems include the satisfiability problem, the travelling salesman problem, and the knapsack problem. A compendium of NP problems is available.