ALGORITHMICS FOR HARD PROBLEMS. PART II. SOME DIFFICULT HEURISRICS

Abstract

In the second part of this paper, we continue to present our views on the hard problems and possible approaches for their algorithmics. The level of presentation is “slightly larger than the popular-science”, but “slightly less than scientific”. We call attention to the fact that we do not restrict our interpretation of hardness to so called NP-hardness in this book. Problems like primality testing, that are not known to be NP-hard (but that are also not known to be polynomial-time solvable), are in the center of our interest, too. It focuses on a systematic presentation of the fundamental concepts and algorithm design techniques. Among the examples of the tasks before us, there are the famous intellectual puzzle games, as well as the travelling salesman problem and problems of minimization of nondeterministic finite automata and disjunctive normal forms. Among the algorithms, we first consider the heuristic, which usually does not guarantee an optimal solution, but with an acceptably high probability yield a solution that is close to it. An important type is the so-called anytime-algorithms, i.e., real-time algorithms that have the best (for now) solution at any given moment; wherein the user in real-time may look these pseudo-optimal solutions, and usually, the sequence of these solutions gives in the limit the optimal one.