Fine hierarchies and m-reducibilities in theoretical computer science (Q949621)

Recall that the oldest and simplest example of a ``fine hierarchy'' is the difference hierarchy introduced and investigated by F. Hausdorff in his book on set theory. Further, the notion of a hierarchy is easily used as a logical tool to unify concepts and measure the complexity of formal objects such as sets in logic, topology, analysis, algebra, and computer science. In this well-written and interesting survey, the author undertakes to explore, in detail, the use of ordinals in hierarchy theory so as to estimate the complexity of sets in several basic areas of computer science. Further, the author summarizes the definitions and results of several versions of the notions of ``fine hierarchies'' and ``many-one reducibilities'' that appear in the computer science literature, thereby clarifying ideas on the complexity of finite and infinite computations. In the process, several unsettled problems are posed. Finally, the author closes with a comprehensive and useful bibliography containing 178 items of international scope.