by William I. Gasarch and Georgia A. Martin
Progress in Computer Science and Applied Logic: Vol. 16 Birkhäuser Boston c/o Springer-Verlag New York, 1999, 353 pages ISBN 0-8176-3966-7
In recursion theory one considers functions which
can be computed by an algorithm. Computational complexity theory is dedicated
to the study of the difficulty of computations based on the notion of a
measure of computational complexity in terms of the amount of some resources
a program uses in a specific computation. An important measure of the complexity
of a computable function is the time needed to compute it. Other
resources, such as space, have also been considered.
The object of the book is to classify functions which are not calculable from the point of view of their difficulty, in a quantitative way. For this, a new notion of complexity that is quantitative is introduced such that it expresses the level of difficulty of a function (such as the Turing degree). This work is a reflection of the contribution of the authors to the foundation and the development of a new direction of research in computational complexity theory.
An oracle Turing machine is defined as a Turing machine together with an extra tape, an extra head to be used for reading that tape, and a mechanism to move the extra head and to overwrite characters on the extra tape. This notion is considered as a model of computation which extends the usual model of Turing machine to the power of asking questions - called queries - about membership in some fixed set X of natural numbers – called an oracle – and getting back correct answers.
The extra tape is used to register queries made by the machine in the course of computation, and to replace the queries by their answers. For a set X, MX denotes an oracle Turing machine together with oracle X. On input x, MX(x) is computed by running the oracle Turing machine using queries. A query to X is a question of the form "y Î X ?". Whenever a number y is written on the extra tape and the QUERY state is entered, y is erased and the value of X(y) - the query answer - fills its place.
Let ¦ be a function which can be computed on an oracle Turing machine. Then the basic notion of complexity introduced by the authors is the number of queries to X required to compute ¦. The aim of the book is to classify different functions in terms of this new notion of complexity and to compare some classes of functions.
Two kinds of theorems are presented in this work. Those expressed by "¦ can be computed with n queries to X but not with n – 1". Other theorems are expressed by "there are functions in class F that are not in class G" and are meant to find out when more queries can be used to compute more functions.
The book is divided into four Parts having ten Chapters. A list of references and an index to notions and symbols are also included.
Part A: Getting Your Feet Wet
Chapter 1: Basic Concepts
Chapter 2: Bounded Queries and the Halting Set
Chapter 3: Definitions and Questions
Part B: The Complexity of Functions
Chapter 4: The Complexity
of
Chapter 5:
and
Other Functions
Part C: The Complexity of Sets
Chapter 6: The Complexity of 
and 
Chapter 7: Q versus QC
Chapter 8: Separating and Collapsing Classes
Part D: Miscellaneous
Chapter 9: Nondeterministic Complexity
Chapter 10: The Literature on Bounded Queries
In Part A basic notions and results from recursion theory and bounded queries are introduced together with some notations used in the book.
In Part B the functions are classified in terms of the
number of queries needed to compute them. The query and enumeration complexities
of some functions are investigated: in Chapter 4 the complexity of
for various n and A is discussed; in Chapter 5 one proves that if
is n-enumerable then A is recursive using a Ramsey-type theorem for
trees; a strong class separation is also presented.
In Part C certain kinds of sets are classified from the point of view of complexity using new notions and latest techniques developed for this purpose.
In Part D other important areas of bounded query research are presented: query complexity of functions computed on non-deterministic Turing machines (Chapter 9) and an annotated bibliography of papers on the topic of bounded-query classes in recursion theory (Chapter 10).
The presentation of the material is very accessible because it is based on intuitive description and discussion before mathematical expression. The book is useful to all the categories of readers interested in computational complexity including graduate students or advanced undergraduate students in mathematics or computer science.
Dr. Mircea Sularia