Structural complexity theory
- This page is about structural complexity theory in computational complexity theory of computer science. For structural complexity in applied mathematics see structural complexity (applied mathematics)
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]
The theory has emerged as a result of (still failing) attempts to resolve the first and still the most important question of this kind, the P = NP problem. Most of the research is done basing on the assumption of P not being equal to NP and on a more far-reaching conjecture that the polynomial time hierarchy of complexity classes is infinite.[1]
Major directions of research in this area include:[1]
- study of implications stemming from various unsolved problems about complexity classes
- study of various types of resource-restricted reductions and the corresponding complete languages
- study of consequences of various restrictions on and mechanisms of storage and access to data
References
- ^ a b c 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.
 | This computer science article is a stub. You can help Wikipedia by expanding it. |