Structural complexity theory
Encyclopedia
In computational complexity theory
of computer science
, the structural complexity theory or simply structural complexity is the study of complexity class
es, 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.
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.
Major directions of research in this area include:
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
of computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the structural complexity theory or simply structural complexity is the study of complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
es, 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.
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.
Major directions of research in this area include:
- study of implications stemming from various unsolved problems about complexity classes
- study of various types of resource-restricted reductionReduction (complexity)In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
s and the corresponding complete languages - study of consequences of various restrictions on and mechanisms of storage and access to data.