Algorithmes et théorie de la complexité structurelle

De nombreux résultats importants dans la théorie de la complexité computationnelle, et en particulier la théorie de la complexité "structurelle", ont la propriété intéressante de pouvoir être compris comme suivant fondamentalement (comme je le vois ...) des résultats algorithmiques donnant un algorithme ou un protocole de communication efficace pour certains. problème. Il s'agit notamment des éléments suivants:

• IP = PSPACE découle d'un algorithme récursif économe en espace simulant des protocoles interactifs et d'un protocole interactif efficace pour évaluer des formules booléennes totalement quantifiées. En fait, toute égalité de classe de complexité A = B peut être considérée comme résultant de deux algorithmes efficaces (un algorithme pour les problèmes dans A qui est efficace par rapport à B, et vice versa).
• Prouver la complétude NP de certains problèmes revient simplement à trouver un algorithme efficace pour y réduire un problème NP-complet.
• L'ingrédient crucial (sans doute!) Du théorème de la hiérarchie temporelle est une simulation universelle efficace des machines de Turing.
• Le résultat récent de Ryan Williams selon lequel ACC NEXP$\not \supset$ est basé sur un algorithme efficace pour résoudre la satisfiabilité des circuits pour les circuits ACC.
• Le théorème du PCP est qu'une amplification efficace de l'écart est possible pour les problèmes de satisfaction des contraintes.
• etc.

Ma question (qui est peut-être désespérément vague!) Est la suivante: y a-t-il des résultats importants dans la théorie de la complexité structurelle (par opposition aux "méta-résultats" comme la barrière de relativisation) qui ne sont pas connus pour avoir une interprétation naturelle en termes d'efficacité algorithmes (ou protocoles de communication)?

Pour de nombreuses bornes inférieures de complexité algébrique, je ne connais pas d'interprétation naturelle en termes d'algorithmes efficaces. Par exemple:

• la technique des dérivées partielles de Nisan et Wigderson

• la technique du rang de Hesse de Mignon et Ressayre (donnant la borne inférieure actuellement la plus connue sur permanent contre déterminant)

• le degré lié de Strassen (et Baur-Strassen)

• la technique des composants connectés de Ben-Or.

Dans tous les résultats ci-dessus, ils semblent vraiment utiliser une propriété des fonctions impliquées, où cette propriété elle-même ne semble pas liée à l'existence d'un algorithme particulier (sans parler d'un algorithme efficace).

Pour les résultats non algébriques, voici quelques réflexions:

• L'argument de comptage standard pour la borne inférieure de tri ne semble pas avoir d'interprétation en termes d'algorithmes efficaces. Cependant, il existe une version contradictoire de cette borne inférieure [1], dans laquelle il existe un algorithme qui, étant donné tout arbre de décision qui utilise trop peu de comparaisons, construit efficacement une liste que l'arbre de décision trie incorrectement. Mais la version contradictoire, bien que pas difficile, est beaucoup plus difficile que la preuve de comptage. (Notez que c'est un peu plus fort que ce que l'on obtient en appliquant la technique de la borne inférieure de l'adversaire, par exemple comme dans ces notes , car dans [1] l'adversaire lui-même est efficace .)$n \log n$

• Je pense que j'ai changé d'avis à propos de PARITY pas dans (même la preuve originale, encore moins la preuve Razborov-Smolensky, comme l'a souligné @RobinKothari). Bien que le lemme de commutation puisse être considéré comme un algorithme randomisé ( ou déterministe ) qui vous permet d'échanger deux lignes d'un circuit sans une grosse explosion, je pense que cela a vraiment une saveur différente de celle de nombreux résultats en complexité, et en particulier la ceux que vous citez. Par exemple, la preuve de Williams que est basée fondamentalement sur l'existence d'un bon algorithme pour un problème particulier. En revanche, si l'on pouvait prouver quelque chose comme le lemme de commutation de manière non constructive, ce serait tout aussi bon pour prouver la PARITE pas dans .$AC^0$$ACC \neq NEXP$$AC^0$

En raison de ces deux derniers exemples - en particulier le tri, où la preuve standard n'est pas constructive - il me semble que la question peut ne pas être seulement sur les interprétations naturelles en termes d'algorithmes efficaces, mais aussi en quelque sorte sur la constructivité / efficacité des preuves de divers résultats de complexité (selon ce que le PO avait en tête). Autrement dit, la borne inférieure de tri standard n'est ni constructive ni algorithmique, mais il existe une preuve algorithmique constructive du même résultat.

[1] Atallah, MJ et Kosaraju, SR Une borne inférieure basée sur l'adversaire pour le tri . Informer. Proc. Lett. 13 (2): 55-57, 1981.