Structural complexity theory

This article is about the area in computer science. For the area in applied mathematics, see Structural complexity (applied mathematics).
Pictorial representation of the polynomial time hierarchy. The arrows denote inclusion.

In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.[1]

  1. ^ Juris Hartmanis, "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming, 1988 (ICALP 88), Lecture Notes in Computer Science, vol. 317 (1988), pp. 271-286.