ABSTRACT
This chapter discusses algorithms and measures of their difficulty. It formulates different approaches to the double digest problem (DDP). The method of solving a computational problem is called an algorithm. Knuth in his classic volumes on The Art of Computer Programming lists five important features of an algorithm that distinguish it from commonly used words like recipe, procedure, and so on. An algorithm must stop after a finite number of steps. This requirement shows the influence of computers; we are not interested in methods that take literally forever. All steps of an algorithm must be precisely defined. The Metropolis algorithm yields a general, that is, problem nonspecific, way to attack many difficult combinatorial optimization problems. In order to implement the simulated annealing algorithm as described above, an energy function and a neighborhood structure are required. The algorithm is probably the most efficient known algorithm for exact data. Alas, it does not perform as well on realistic data.
