On the Structure of Feasible Computations

Abstract

During the last four years research on the lower level computational complexity has yielded a rich set of interesting results which have revealed deep and unexpected connections between various problems and thus brought new unity to this area of computer science. This work has also yielded new techniques and insights which are likely to have further applications, and it has identified some very central problems in the quantitative theory of computing. The purpose of this paper is to give the reader an overview of these developments, an insight into some of these results and applications, as well as an appreciation of the unity and structure which has emerged in this area of research.