I am new to complexity theory and want to know what is structural complexity theory? what are problems theorists try to solve in this field and what is its future? From the wikipedia:

The structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms

I did not get the last line "rather than computational complexity of individual problems and algorithms " I mean in complexity theory we focus on complexity classes not on problems.

Thanks in advance

  • $\begingroup$ The Wikipedia statement seems clear enough, so what is perhaps missing is a term indicating that one is referring to complexity of problems rather than classes. Computational_complexity_theory in Wikipedia says if focusses on “classifying … problems … and relating … classes”, so it seems to cover both, though it sounds as though it could be used in a narrow sense for only the first. $\endgroup$ – PJTraill Sep 23 '17 at 13:01

Structural complexity theory studies the relation between different complexity classes, usually uniform ones. The two most famous open questions in the field are:

Is $\mathsf{P} \neq \mathsf{NP}$?

Is $\mathsf{P} = \mathsf{BPP}$?

In the past, a common pursuit in structural complexity theory was coming up with oracles that separate or join complexity classes. For example, people came up with oracles relative to which $\mathsf{P} = \mathsf{NP}$, and other oracles relative to which $\mathsf{P} \neq \mathsf{NP}$. This type of activity seems less popular now. Diagonalization is another common proof technique that used to be more popular in the past, but is somewhat less popular today.

Another common pursuit is proving conditional results. For example, Buhrman, Chang and Fortnow show that if $\mathsf{coNP} \subseteq \mathsf{NP/1}$ then the polynomial hierarchy collapses. Since it is conjectured that the polynomial hierarchy is strict (doesn't collapse), it follows that probably $\mathsf{coNP} \not\subseteq \mathsf{NP/1}$.

What are some similar results that are not considered structural complexity theory? Here are some examples:

  • Results in circuit complexity. For example, $\mathsf{AC^0} \neq \mathsf{P}$ is not classical structural complexity theory.

  • Results about specific problems, for example NP-completeness of specific problems.

Other results could in principle be considered structural complexity theory, but because the techniques used are so different than classical results in structural complexity theory, they are not usually thought of as structural complexity theory. Conspicuous examples include:

  • $\mathsf{IP} = \mathsf{PSPACE}$, which uses algebraization. This is a borderline example.
  • The PCP theorem, which uses ideas from coding theory.

The above is just my own opinion. Other people might have very different opinions. Structural complexity theory is not a codified area of research.


For example, a problem may be shown to be NP-Complete. Yet this is not what aimed in structural complexity theory, because it does not tell anything new about the structure of complexity classes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.