O que é a teoria da complexidade estrutural?

Eu sou novo na teoria da complexidade e quero saber o que é a teoria da complexidade estrutural? quais são os problemas que os teóricos tentam resolver nesse campo e qual é o seu futuro? Da wikipedia:

A teoria da complexidade estrutural ou simplesmente a complexidade estrutural é o estudo de classes de complexidade, em vez da complexidade computacional de problemas e algoritmos individuais

Eu não entendi a última linha "em vez da complexidade computacional de problemas e algoritmos individuais", quero dizer que na teoria da complexidade nos concentramos em classes de complexidade e não em problemas.

desde já, obrigado

A teoria da complexidade estrutural estuda a relação entre diferentes classes de complexidade, geralmente uniformes. As duas questões abertas mais famosas no campo são:

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

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

No passado, uma busca comum na teoria da complexidade estrutural estava surgindo com oráculos que separam ou juntam classes de complexidade. Por exemplo, as pessoas criaram oráculos em relação aos quais$\mathsf{P} = \mathsf{NP}$e outros oráculos em relação aos quais $\mathsf{P} \neq \mathsf{NP}$. Esse tipo de atividade parece menos popular agora. A diagonalização é outra técnica de prova comum que costumava ser mais popular no passado, mas hoje é um pouco menos popular.

Outra busca comum é provar resultados condicionais. Por exemplo, Buhrman, Chang e Fortnow mostram que se$\mathsf{coNP} \subseteq \mathsf{NP/1}$então a hierarquia polinomial entra em colapso. Como é suposto que a hierarquia polinomial é estrita (não entra em colapso), segue-se que provavelmente$\mathsf{coNP} \not\subseteq \mathsf{NP/1}$.

Quais são alguns resultados semelhantes que não são considerados teoria da complexidade estrutural? aqui estão alguns exemplos:

• Resulta na complexidade do circuito. Por exemplo, não é uma teoria clássica da complexidade estrutural.$\mathsf{AC^0} \neq \mathsf{P}$

• Resultados sobre problemas específicos, por exemplo, NP-completude de problemas específicos.

Outros resultados poderiam, em princípio, ser considerados teoria da complexidade estrutural, mas, como as técnicas utilizadas são muito diferentes dos resultados clássicos na teoria da complexidade estrutural, elas geralmente não são consideradas como teoria da complexidade estrutural. Exemplos conspícuos incluem:

• $\mathsf{IP} = \mathsf{PSPACE}$ , que usa algebraização. Este é um exemplo limítrofe.
• O teorema do PCP, que usa idéias da teoria da codificação.

O acima é apenas minha própria opinião. Outras pessoas podem ter opiniões muito diferentes. A teoria da complexidade estrutural não é uma área de pesquisa codificada.

Por exemplo, um problema pode ser mostrado como NP-Complete. No entanto, não é isso que visa a teoria da complexidade estrutural, porque não diz nada de novo sobre a estrutura das classes de complexidade.