Classical complexity theory has concentrated on studying problems that have yes/no answers--that is, 0-1 functions. Both classical recursive function theory and optimization theory have studied more general functions, however. For example, given a graph G, the traveling salesperson problem asks for a cycle that visits each vertex in G exactly once and minimizes the sum of the edge costs; the 0-1 version asks, given G and an integer k, is there a tour whose cost is less than or equal to k ? In some sense, nothing is lost by considering the 0-1 version of the problem, and it is often much easier to analyze 0-1 functions. Nevertheless, this paper continues the attempt by the author and other researchers to capture more structure in NP by considering a wider class of problems as functions.

The author previously defined Opt P as a class of functions computed from nondeterministic machines by applying a max or min operator to the branches of a computation tree. Here, Opt P is extended to the polynomial hierarchy by considering machines with k alternations of max/min (rather than alternations of and/or). The author gives complete problems for two and three levels of alternation. These complete problems involve questions about finite sets of integers, namely integer expressions and sums of subsets. In addition, the author shows that a class of functions computable with an unbounded (but still polynomial) number of alternations is equivalent to a restricted class of functions computable in polynomial space.

The paper is well written, although some of the notation is a bit confusing. One major contribution of the paper is the author’s success in drawing together a number of disparate areas, including alternating Turing machines and the polynomial hierarchy, context-free grammars, optimization theory, and game theory.