Constructive complexity

Powerful and widely applicable, yet inherently nonconstructive, tools have recently become available for classifying decision problems as solvable in polynomial time, as a result of the work of Robertson and Seymour. These developments challenge the established view that equates tractability with polynomial-time solvability, since the existence of an inaccessible algorithm is of very little help in solving a problem. In this paper, the authors attempt to provide the foundations for a constructive theory of complexity, in which membership of a problem in some complexity class indeed implies that they can find out how to solve that problem within the stated bounds. The present approach is based on relations, rather than on sets; the authors make much use of self-reducibility and oracle machines, both conventional and ‘blind’, to derive a series of results which establish a structure similar to that of classical complexity theory, but in which they are in fact able to prove results which remain conjectural within the classical theory.