Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory
Ronald V. Book · SIAM Review · 1994
The notion of NP-completeness has helped researchers in several fields to argue that some problems are intrinsically difficult to solve computationally, even though proof of that is beyond the current state of our knowledge. The study of properties of complete sets and reducibilities has led to the development of a branch of complexity theory called structural complexity theory. This paper is a brief survey of recent results in structural complexity theory and is aimed at researchers who know something about computational complexity theory but do not work in structural complexity theory. To describe the theory in a way that gives the reader some concrete applications, the results are described in terms of their relationship to P =?NP and other problems.