×

A view of structural complexity theory. (English) Zbl 0709.68017

At several recent conferences, the question “What is Structural Complexity Theory?” has been the source of some lively discussions. At this time there does not exist one commonly accepted answer but the intersection of almost all answers is nonempty. The purpose of this paper is to describe one answer to this question. We will not describe in detail recent technical results, although some will be mentioned as examples, but rather will provide comments about themes and paradigms which may be used to help organize much of the material.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite