HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

What is structural complexity theory?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theorystructuralcomplexitywhat

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#81469, answer score: 14

Revisions (0)

No revisions yet.