Structural complexity theory
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 != 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.
See also
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.