Structural complexity theory
Structural complexity theory, or simply structural complexity, is a branch of computational complexity theory in computer science. In structural complexity the main focus is on complexity classes, as opposed to the study of how individual problems behave, or the analysis of individual algorithms. Structural complexity investigates both internal structures of complexity classes, and relations that hold between different complexity classes.[1]
Structural complexity theory has emerged as a result of attempts to resolve the first and still the most important question of this kind, the P = NP problem. Most research in structural complexity is done based on the assumption that P != NP, or the stronger conjecture that the polynomial time hierarchy of complexity classes is infinite.[1]
Major directions of research in this area include:[1]
- conditional results, based on various relationships between complexity classes,
- resource-restricted reductions and the corresponding complete languages, and
- consequences of various restrictions on and mechanisms of storage and access to data.
See also
References
- ^ a b c Hartmanis, Juris (1988). "New Developments in Structural Complexity Theory (invited lecture)". ICALP 1988: Proc. 15th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 317. pp. 271–286.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help)