Techniques avancées pour déterminer les limites inférieures de la complexité

Certains d'entre vous ont peut-être suivi cette question , qui a été fermée en raison d'un niveau de recherche insuffisant. J'extrais donc la partie de la question qui se situe au niveau de la recherche.

Au-delà des techniques "plus simples", telles que la réduction au tri ou un problème EXPTIME-complet, quelles techniques ont été utilisées pour prouver les limites inférieures de la complexité temporelle d'un problème?

En particulier:

• Quelles sont les techniques "de pointe" qui ont été développées au cours de la dernière décennie?
• Peut-on appliquer des techniques de l'algèbre abstraite, de la théorie des catégories ou d'autres branches des mathématiques généralement «pures»? (Par exemple, j'entends souvent parler de la "structure algébrique" du tri, sans aucune explication réelle de ce que cela signifie.)
• Quels sont les résultats significatifs mais moins connus pour la complexité des limites inférieures?

Limites inférieures pour les circuits algébriques

Dans le contexte des circuits algébriques, où une borne inférieure sur la taille du circuit est analogue à une borne inférieure dans le temps, de nombreux résultats sont connus, mais il n'y a que quelques techniques de base dans les résultats les plus modernes. Je sais que vous avez demandé des limites inférieures de temps, mais je pense que dans de nombreux cas, l'espoir est que les limites inférieures algébriques mèneront un jour aux limites inférieures de la machine booléenne / de Turing. Ces résultats utilisent souvent des techniques plus profondes de "mathématiques pures" comme vous dites.

I. Le degré lié.

Strassen a montré que le logarithme du degré d'une certaine variété algébrique associée à un (ensemble de) fonction (s) est une borne inférieure de la taille du circuit algébrique du calcul de ces fonctions.

II. Composants connectés (ou plus généralement la dimension de tout groupe d'homologie supérieur).

Ben-Or a montré que la taille d'un arbre de décision algébrique réel décidant de l'appartenance à un ensemble (semi-algébrique) est au moins où C est le nombre de composants connectés de cet ensemble. Ben-Or a utilisé cela pour prouver une borne inférieure Ω ( n log n ) lors du tri (enfin, la distinction des éléments, mais la distinction des éléments se réduit au tri) dans le modèle d'arbre de décision algébrique réel. Yao a étendu cela des composants connectés à la somme des nombres de Betti et a démontré des limites inférieures optimales pour d'autres problèmes (comme les k -equals)). Dans un autre article, Yao a étendu cela aux arbres de décision algébriques sur les entiers.$\log C$$C$$\Omega(n \log n)$$k$

III. Dérivés partiels.

Cela a été le cheval de bataille de la plupart des limites inférieures du circuit algébrique moderne. Je crois que les dérivées partielles ont d'abord été utilisées pour prouver une borne inférieure par Baur-Strassen, où elles ont montré que le calcul de tous les premiers partiels de peut être fait en taille 5 s où s est la taille nécessaire pour calculer f . Combiné à la borne de degré de Strassen, cela a donné des bornes inférieures de taille Ω ( n log n ) sur diverses fonctions, qui sont toujours les bornes inférieures les plus fortes sur la taille des circuits arithmétiques sans restriction pour une fonction explicite.$f$$5s$$s$$f$$\Omega(n \log n)$

L'utilisation plus récente des dérivées partielles semble provenir d'un article de Nisan dans lequel il a prouvé des bornes inférieures sur des circuits non commutatifs en considérant la dimension de l'espace de toutes les dérivées partielles. Cela a été utilisé pour prouver les limites inférieures sur des types restreints de circuits de profondeur 3 par Nisan-Wigderson, et des idées similaires ont été utilisées pour prouver les limites inférieures sur la taille des formules multilinéaires par Raz (et les modèles connexes par Raz et ses collaborateurs). Les très récentes limites inférieures de profondeur 4 et de profondeur 3 de Gupta, Kayal, Kamath et Saptharishi utilisent une généralisation de cette idée, pour compter la dimension de l'espace des "dérivées partielles décalées" - où vous pouvez prendre des dérivées partielles et ensuite multiplier par tous les monômes d'un degré donné. ) peut "simplement" être une question de mieux comprendre l'idéal généré par les mineurs permanents (voir la conjecture à la fin de leur article).$\mathrm{VP} \neq \mathrm{VNP}$

IV. Définir des équations pour les variétés.

L'idée ici est d'associer aux "fonctions faciles" une certaine variété algébrique, de trouver des équations qui disparaissent sur cette variété, et de montrer que ces équations ne disparaissent pas sur votre "fonction dure". (Prouvant ainsi que votre fonction difficile n'est pas dans la variété des fonctions faciles, de sorte qu'elle est réellement difficile.) Particulièrement utile dans les limites inférieures de la multiplication matricielle. Voir Landsberg - Ottaviani sur l'arXiv pour la dernière version et les références aux bornes inférieures antérieures.

(En fait, I, II et III ci-dessus peuvent tous être considérés comme des cas particuliers de recherche d'équations de définition pour certaines variétés, bien que les preuves qui utilisent I, II, III ne soient essentiellement jamais formulées de cette façon, car il n'y avait pas vraiment de besoin de.)

V. Théorie de la représentation, esp. comme dans la théorie de la complexité géométrique.

En fait, également utilisé par Landsberg - Ottaviani pour trouver des équations pour une certaine variété. Également utilisé par Burgisser-Ikenmeyer pour obtenir une preuve "purement" théorique de représentation d'une borne inférieure légèrement plus faible sur la multiplication matricielle. Conjecturé par Mulmuley et Sohoni (cf. "Théorie de la complexité géométrique I & II") pour être utile pour résoudre vs V N P et finalement N P vs P / p o l y .$\mathrm{VP}$$\mathrm{VNP}$$\mathrm{NP}$$\mathrm{P/poly}$

Kaveh a gentiment suggéré dans sa réponse que je devrais dire quelque chose. Je n'ai pas grand-chose d'autre à apporter à cette liste de réponses très complète. Je peux ajouter quelques mots génériques sur l'évolution des bornes inférieures de la "complexité structurelle" au cours des dix dernières années. (J'utilise le nom de "complexité structurelle" simplement pour distinguer l'algèbre, la complexité de la communication, etc.)

Les approches actuelles sont encore largement basées sur la diagonalisation, et en particulier le paradigme de base suivant: Commençons par supposer l'opposé de la borne inférieure. Cela vous donne un bon algorithme pour certains problèmes. Essayez d'utiliser cet algorithme pour contredire un théorème de hiérarchie basé sur la diagonalisation, comme la hiérarchie temporelle ou la hiérarchie spatiale. Comme les arguments de diagonalisation ne suffisent pas à eux seuls à prouver de nouvelles limites inférieures, d'autres ingrédients sont ajoutés au mélange afin d'obtenir la recette contradictoire.

Je dois dire que de nombreux arguments des années 70 et 80 suivent également le schéma ci-dessus; la principale différence de nos jours est les "autres ingrédients" - il y a beaucoup d' ingrédients parmi lesquels choisir, et les façons dont les ingrédients peuvent être appliqués ne semblent limitées que par votre propre créativité. Parfois, lorsque vous ne savez pas comment mélanger des ingrédients particuliers pour obtenir une meilleure recette, mais que vous comprenez très bien comment ils peuvent se mélanger, cela aide à coder un programme informatique qui vous suggère de nouvelles recettes.

Il serait très intéressant d'obtenir de nouvelles preuves de limites inférieures récentes qui ne suivent définitivement pas ce paradigme. Par exemple, peut-il être prouvé sans référence à un argument de diagonalisation? Pour commencer, peut-on le prouver sans invoquer le théorème de la hiérarchie temporelle non déterministe? (Peut-on utiliser à la place la "hiérarchie des tailles de circuits", par exemple?)$NEXP \not\subset ACC$

Les techniques dépendent du modèle et du type de ressource que nous voulons obtenir une borne inférieure. Notez que pour prouver une borne inférieure sur la complexité d'un problème, nous devons d'abord fixer un modèle mathématique de calcul: une borne inférieure pour un problème est qu'aucun algorithme utilisant une certaine quantité de ressources ne peut résoudre le problème, c'est-à-dire que nous quantifions universellement sur des algorithmes. Nous devons avoir une définition mathématique du domaine de la quantification. (Cela est généralement vrai pour les résultats d'impossibilité.) Par conséquent, les résultats de la borne inférieure ne s'appliquent qu'à un modèle de calcul particulier. Par exemple, le $\Omega(n \log n)$La borne inférieure pour le tri ne fonctionne que pour les algorithmes de tri basés sur la comparaison, sans cette restriction et dans des modèles de calcul plus généraux, il pourrait être possible de résoudre le tri plus rapidement, même le temps linéaire. (Voir le commentaire de Josh ci-dessous.)

Voici quelques méthodes directes de base pour prouver les bornes inférieures dans la théorie de la complexité de calcul pour les modèles plus généraux de calcul (machines et circuits de Turing).

I. Comptage:

Idée: Nous montrons qu'il y a plus de fonctions que d'algorithmes.

Ex: Certaines fonctions nécessitent des circuits exponentiellement grands.

Le problème avec cette méthode est qu'elle est un argument existentiel et ne donne aucune fonction explicite ni aucune limite supérieure sur la complexité du problème avéré difficile.

II. Combinatoire / algébrique:

Idée: Nous analysons les circuits et montrons qu'ils ont une propriété particulière, par exemple les fonctions calculées par eux peuvent être approximées par une belle classe d'objet mathématique, tandis que la fonction cible n'a pas cette propriété.

Ex: le lemme de commutation de Håstad et ses variantes utilisent l'arbre de décision pour approximer , Razborov-Smolensky utilise des polynômes sur les champs pour approximer les fonctions A C 0 [ p ] , etc.$\mathsf{AC^0}$$\mathsf{AC^0}[p]$

Le problème avec cette méthode est qu'en pratique, elle n'a fonctionné que pour des classes petites et relativement faciles à analyser. Il existe également la barrière des preuves naturelles de Razborov-Rudich qui formalise en quelque sorte pourquoi les propriétés simples en elles-mêmes ne sont probablement pas suffisantes pour prouver des limites inférieures de circuit plus générales.

L'article de Razborov « Sur la méthode d'approximation » soutient que la méthode d'approximation est complète pour prouver les limites inférieures dans un sens.

III. Diagonalisation:

Idée. Nous diagonalisons par rapport aux fonctions de la classe plus petite. L'idée remonte à Gödel (et même à Cantor).

Ex. Théorèmes de hiérarchie temporelle , théorème de hiérarchie spatiale , etc.

Le principal problème avec cette méthode est que pour obtenir une limite supérieure, nous devons avoir un simulateur universel pour la classe plus petite et il est difficile de trouver de bons simulateurs non triviaux. Par exemple, pour séparer de P S p a c e, nous devons avoir un simulateur pour P à l' intérieur de P S p a c e et des résultats montrent que s'il existe de tels simulateurs, ils ne seront pas agréables. Par conséquent, nous nous retrouvons généralement avec des classes séparées avec le même type de ressources, où en utilisant un peu plus de ressources, nous pouvons simuler universellement la classe la plus petite.$\mathsf{P}$$\mathsf{PSpace}$$\mathsf{P}$$\mathsf{PSpace}$

Nous avons également la barrière de relativisation (remontant à Baker, Gill et Solovay) et la barrière d'algèbre (par Aaronson et Wigderson) qui stipulent que des types particuliers d'arguments de diagonalisation seront transférés vers d'autres paramètres où le résultat est manifestement faux.

Notez que ces barrières ne s'appliquent pas aux arguments de diagonalisation plus généraux. En fait, selon l'article de Dexter Kozen « Indexation des classes subrécursives », la diagonalisation dans est complète pour prouver les bornes inférieures.

Comme vous l'avez probablement remarqué, il existe une relation étroite entre trouver de bons simulateurs universels pour une classe de complexité et séparer cette classe de complexité des classes plus grandes (pour une déclaration formelle, voir l'article de Kozen).

Travaux récents

Pour les avancées récentes, consultez les articles récents de Ryan Williams . Je n'en parle pas dans cette réponse car j'espère que Ryan lui-même écrira une réponse.

Arbres de décision algébriques

Ce n'est pas une technique récente, mais assez puissante pour certains problèmes.

Le modèle d'arbre de décision algébrique est une puissante généralisation des arbres de comparaison. Dans ce modèle, un algorithme est modélisé comme une famille non uniforme d'arbres de décision, un pour chaque taille d'entrée . Plus précisément, un arbre de décision algébrique d'ordre d est un arbre ternaire enraciné avec la structure suivante:$n$$d$

• Chaque nœud non feuille est étiqueté avec un polynôme de requête multivarié q v ( x 1 , … , x n ) de degré au plus d . Par exemple, dans un arbre de comparaison, chaque polynôme de requête a la forme x i - x j pour certains indies i et j .$v$$q_v(x_1, \dots, x_n)$$d$$x_i-x_j$$i$$j$

• Les bords quittant chaque nœud non feuille sont étiquetés , 0 et + 1 .$-1$$0$$+1$

• Chaque feuille est étiquetée avec une description de sortie possible. Par exemple, pour le problème de tri, chaque feuille est étiquetée avec une permutation de l'ensemble . Pour les problèmes de décision, chaque feuille est étiquetée "oui" ou "non".$\{1,2,\dots,n\}$

Étant donné un vecteur d'entrée , nous calculons en parcourant un chemin vers le bas à partir de la racine, en ramifiant selon le signe des polynômes de requête dans les nœuds visités. La traversée atteint finalement une feuille; l'étiquette de cette feuille est la sortie. Le "temps d'exécution" de l'algorithme est défini comme étant la longueur du chemin parcouru; ainsi, le temps d'exécution le plus défavorable est la profondeur de l'arbre de décision.$\vec{x}\in\mathbb{R}^n$

$\Omega(n^d)$

$\ell$$R(\ell) \subseteq \mathbb{R}^n$$\ell$$R(\ell)$$\mathbb{R}^n$$t = \text{depth}(\ell)$$d$$d$$(dt)^{O(n)}$

$W\subseteq\mathbb{R}^n$$d$$t$$W$$3^t (dt)^{O(n)}$$t = \Omega(\log \#W - n\log d)$

$n$$W$$n!$$n$$\Omega(n\log n)$

$\Omega(n\log n)$

$R(\ell)$$(dt)^{O(n)}$

$n^{O(n)}$$n\log n$

$\Omega(n^2)$$O(n^4\log n)$$2^{O(n)}$$\mathbb{R}^n$$n^4\log n$$k$$k$$k$$k$$O(n^{k/2})$$O(n^4\log n)$interroger les polynômes; ce temps de construction est libre dans le modèle de borne inférieure.

Hourra pour des résultats doubles négatifs!

Manindra Agrawal a un beau papier "Prouver des limites inférieures via des générateurs aléatoires". Cela pourrait être considéré comme un «cheval noir» en lice pour prouver les limites inférieures, mais le document est intéressant.

il s'agit d'une enquête 32p qui vient d'apparaître sur le sujet en se concentrant sur l'angle des limites inférieures du circuit (il y a un fort chevauchement dans le contenu avec d'autres réponses ici).

• Algorithmes contre limites inférieures du circuit par Oliveira

Différentes techniques ont été utilisées pour prouver plusieurs théorèmes de transfert de la forme «des algorithmes non triviaux pour un circuit de classe C produisent des limites inférieures de circuit contre C». Dans cette enquête, nous revisitons bon nombre de ces résultats. Nous discutons de la façon dont les limites inférieures du circuit peuvent être obtenues à partir d'algorithmes de dérandomisation, de compression, d'apprentissage et de satisfiabilité. Nous couvrons également la connexion entre les bornes inférieures du circuit et les propriétés utiles, notion qui s'avère fondamentale dans le contexte de ces théorèmes de transfert. En cours de route, nous obtenons quelques nouveaux résultats, simplifions plusieurs preuves et montrons des connexions impliquant différents frameworks. Nous espérons que notre présentation servira d'introduction autonome pour ceux qui souhaitent poursuivre des recherches dans ce domaine.