Qu'est-ce que la théorie de la complexité structurelle?

Je suis nouveau dans la théorie de la complexité et je veux savoir ce qu'est la théorie de la complexité structurelle? quels problèmes les théoriciens tentent-ils de résoudre dans ce domaine et quel est son avenir? Du wikipedia:

La théorie de la complexité structurelle ou simplement la complexité structurelle est l'étude des classes de complexité, plutôt que la complexité de calcul des problèmes individuels et des algorithmes

Je n'ai pas obtenu la dernière ligne "plutôt que la complexité de calcul des problèmes individuels et des algorithmes". Je veux dire que dans la théorie de la complexité, nous nous concentrons sur les classes de complexité et non sur les problèmes.

Merci d'avance

La théorie de la complexité structurelle étudie la relation entre différentes classes de complexité, généralement uniformes. Les deux questions ouvertes les plus connues dans le domaine sont:

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

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

Dans le passé, une recherche commune dans la théorie de la complexité structurelle consistait à trouver des oracles qui séparent ou rejoignent les classes de complexité. Par exemple, les utilisateurs ont trouvé des oracles par rapport à quel , et d'autres oracles par rapport à quel . Ce type d'activité semble aujourd'hui moins populaire. La diagonalisation est une autre technique de preuve courante qui était plus populaire dans le passé, mais qui l'est un peu moins aujourd'hui.$\mathsf{P} = \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Une autre poursuite courante consiste à prouver des résultats conditionnels. Par exemple, Buhrman, Chang et Fortnow montrent que si alors la hiérarchie polynomiale s'effondre. Puisqu'on suppose que la hiérarchie polynomiale est stricte (ne s'effondre pas), il s'ensuit que probablement .$\mathsf{coNP} \subseteq \mathsf{NP/1}$$\mathsf{coNP} \not\subseteq \mathsf{NP/1}$

Quels sont les résultats similaires qui ne sont pas considérés comme une théorie de la complexité structurelle? Voici quelques exemples:

• Entraîne une complexité du circuit. Par exemple, n'est pas une théorie de complexité structurelle classique.$\mathsf{AC^0} \neq \mathsf{P}$

• Résultats sur des problèmes spécifiques, par exemple NP-exhaustivité de problèmes spécifiques.

D'autres résultats pourraient en principe être considérés comme une théorie de la complexité structurelle, mais comme les techniques utilisées sont si différentes des résultats classiques de la théorie de la complexité structurelle, ils ne sont généralement pas considérés comme une théorie de la complexité structurelle. Des exemples remarquables comprennent:

• $\mathsf{IP} = \mathsf{PSPACE}$ , qui utilise l'algèbre. Ceci est un exemple limite.
• Le théorème du PCP, qui utilise des idées de la théorie du codage.

Ce qui précède n'est que ma propre opinion. D'autres personnes peuvent avoir des opinions très différentes. La théorie de la complexité structurelle n'est pas un domaine de recherche codifié.

Par exemple, un problème peut apparaître comme NP-Complete. Pourtant, ce n'est pas ce que vise la théorie de la complexité structurelle, car elle ne dit rien de nouveau sur la structure des classes de complexité.