Comment prouver qu’un problème est un problème VPN ? Les informaticiens ont trouvé un moyen simple

Le problème P/NP est un problème non résolu dans le domaine de la complexité informatique. Les gens ont essayé de trouver la réponse à une question : « Pouvons-nous résoudre efficacement tous les problèmes informatiques dans un délai raisonnable ? »

Qu'est-ce qu'un délai raisonnable ? En fait, les problèmes qui peuvent être résolus avant la fin de l’univers sont envisagés dans un délai raisonnable. Pourtant, de nombreux problèmes semblent difficiles à résoudre dans un délai raisonnable, ce qui oblige les mathématiques à démontrer la difficulté de ces problèmes.

Une étude de 2021 répond à la question ci-dessus, ce qui confirme : Une grande partie des problèmes sont difficiles à résoudre efficacement.

Paul Beame de l'Université de Washington a commenté cette recherche : "Comme gravir une montagne, cette recherche est un point d'arrêt sur le chemin de la recherche en théorie computationnelle."

Les trois chercheurs de la recherche : des informaticiens Srikanth Srinivasan (à gauche), Nutan Limaye (en haut à droite) et Sébastien Tavenas.

L'étude a examiné des problèmes impliquant uniquement l'addition et la multiplication, mais ils deviennent très difficiles lorsque ces problèmes se limitent à être résolus d'une manière spécifique (un certain modèle alterné d'addition et de multiplication).

Étonnamment, l'étude n'a pas utilisé de nouveau cadre ou outil, les auteurs ont réussi à contourner des décennies de travail décrit par Wigderson, professeur à l'École de mathématiques de l'Institute for Advanced Study de Princeton, en collaboration avec Noam Nisan. à l'Université hébraïque de Jérusalem.

L'un des chercheurs, Srikanth Srinivasan de l'Université d'Aarhus au Danemark, a déclaré : « Nous avons réalisé qu'il existe un moyen très simple de contourner cet obstacle. Et si une méthode aussi simple pouvait être utilisée pour faire ce que nous pensions impossible , alors il doit y avoir une meilleure solution. "

Question importante

Après l'avènement des ordinateurs, les scientifiques ont découvert que les algorithmes informatiques peuvent résoudre de nombreux problèmes, mais parfois ces algorithmes prennent trop de temps - plus longtemps que le temps de calcul réel. .

Ils commencent à soupçonner que certains problèmes sont intrinsèquement trop difficiles à résoudre, quelle que soit leur taille. Par exemple, dans les graphiques, un problème important consiste à déterminer s’il existe un chemin hamiltonien, c’est-à-dire s’il existe un chemin passant par chaque sommet exactement une fois. L'augmentation du nombre de sommets (et d'arêtes) devrait prendre plus de temps pour déterminer si un tel chemin existe, mais même les meilleurs algorithmes prennent un temps exponentiellement plus long à mesure que la taille du graphique augmente, ce qui rend la résolution de ce problème irréaliste.

Les informaticiens tentent de prouver que tout algorithme capable de résoudre efficacement un problème difficile d'un certain type de problème d'une manière ou d'une autre peut être transformé en une solution à d'autres problèmes tout aussi difficiles. Ils appellent ce type de problème problème NP.

Bien sûr, il existe aussi de nombreux problèmes qui ne semblent pas difficiles et ne prennent pas trop de temps à résoudre. Beaucoup de ces problèmes sont également équivalents dans un certain sens, et ces problèmes sont appelés problèmes P. Ils soutiennent que les problèmes NP sont en effet plus difficiles que les problèmes P et que les problèmes NP ne peuvent jamais être résolus efficacement. Mais sans preuves, cette idée pourrait être fausse.

Les informaticiens ont donc commencé à chercher des moyens de prouver que les problèmes NP sont effectivement plus difficiles. Cela nécessitait de prouver que les problèmes NP doivent prendre un temps exponentiel à résoudre, mais prouver que cela n'est pas facile.

À quel point est-ce que « dur » est difficile ?

Imaginez un ensemble spécifique de problèmes qui ne nécessitent que des additions et des multiplications. Par exemple, étant donné un ensemble de points, il est possible de calculer tous les chemins hamiltoniens possibles (s'ils existent) en utilisant les données sur les points, simplement par addition et multiplication.

À mesure que la taille du problème augmente, certains problèmes arithmétiques (tels que le calcul des chemins hamiltoniens) prennent plus de temps. En 1979, Leslie Valiant de l'Université Harvard a montré que de nombreux problèmes arithmétiques sont équivalents en termes de difficulté, tandis que d'autres sont équivalents en termes d'absence de difficulté. Les informaticiens ont ensuite donné son nom à ces deux types de problèmes, respectivement VNP et VP.

Et P Comme le problème NP, nous ne pouvons pas prouver la difficulté du problème VNP. Nous savons seulement que le problème VNP est plus difficile que le problème NP car il est basé sur ce dernier. Par exemple, calculer un chemin nécessite d'abord de déterminer si. le chemin existe.

« C’est plus difficile que NP, donc il devrait être plus facile de montrer que c’est difficile », a déclaré Shpilka.

Au cours des décennies suivantes, les informaticiens ont fait des progrès beaucoup plus importants sur le problème VP contre VNP que sur le problème P contre NP, mais la plupart se limitaient à ce que Valiant a créé, appelé sous-champs de complexité algébrique. Avant les travaux récents de Limaye, Srinivasan et Tavenas, il était encore difficile de dire s'il y avait des problèmes en arithmétique au sens général.

Ajustement des polynômes

Ce nouveau travail permet d'explorer la façon dont les informaticiens réfléchissent aux problèmes d'addition et de multiplication. Mathématiquement, ces problèmes peuvent être écrits en termes de polynômes (par exemple x^2 + 5y + 6) constitués de variables ajoutées et multipliées.

Pour tout problème particulier, comme le calcul d'un chemin hamiltonien, vous pouvez construire un polynôme qui le représente. Par exemple, vous pouvez utiliser une variable pour représenter chaque point et chaque arête, de sorte qu'à mesure que davantage de points et d'arêtes sont ajoutés, davantage de variables puissent être ajoutées au polynôme.

Pour montrer qu'un problème arithmétique comme le calcul d'un chemin hamiltonien est difficile, il faut montrer que plus on ajoute de points et d'arêtes, plus les polynômes correspondants nécessitent plus d'opérations pour être résolus en temps exponentiel. Par exemple, x^2 nécessite une opération (x * x), tandis que x^2 + y nécessite deux opérations (x * x plus y). Le nombre d'opérations est appelé taille du polynôme.

Mais la taille du polynôme est difficile à déterminer. Par exemple le polynôme x^2 + 2x + 1. Il semble avoir une taille de 4 (deux multiplications et deux additions), mais le polynôme peut être réécrit comme le produit de deux sommes, (x + 1)(x + 1), qui a moins d'opérandes - deux fois l'addition, une multiplication. Souvent, à mesure qu’un problème s’agrandit et que davantage de variables sont ajoutées au polynôme, les transformations mathématiques peuvent aider à simplifier et à réduire sa taille.

Quelques années après les recherches de Valiant, des informaticiens ont trouvé un moyen de faciliter l’analyse de l’ampleur du problème. Pour ce faire, ils ont proposé une propriété appelée « profondeur », qui spécifie le nombre de fois où le polynôme bascule ou alterne entre sommes et produits. Par exemple, le polynôme x^2 + 2x + 1 a une profondeur de 2 car il s'agit de la somme de produits (tels que x^2 et 2x). En revanche, l'expression (x + 1)(x + 1) a une profondeur de 3 car elle a la même profondeur que 0 + (x + 1)(x + 1), calculée comme la somme des produits.

Pour simplifier les polynômes, les informaticiens les contraignent à une forme fixe avec une propriété appelée « profondeur constante », où le modèle des sommes et des produits ne change pas à mesure que le problème grandit. Cela les rend de taille plus fixe, la taille du polynôme diminuant à mesure que sa profondeur augmente. Une expression pour une profondeur constante s’appelle une formule. Une profondeur constante permet de progresser davantage dans l'étude des polynômes.

"Profondeur" magique

En 1996, un article de Nisan et Wigderson s'est concentré sur la résolution du problème de la multiplication matricielle. Ils ont simplifié ce problème de deux manières. Tout d’abord, ils l’ont exprimé en utilisant la formule de profondeur constante – une profondeur de 3. Deuxièmement, ils n’ont considéré que des formules ayant une structure simple dans lesquelles chaque variable a un exposant maximum de 1, ce qui fait du problème initial un problème « multilinéaire ».

Les informaticiens ont découvert que certains problèmes peuvent être convertis en structures ensemble-multilinéaires relativement simples au détriment d'une augmentation sous-exponentielle de la taille du polynôme (comparable au taux de croissance de la croissance exponentielle).

Nisan et Wigderson ont montré plus tard que le problème de multiplication matricielle prend un temps exponentiel à résoudre à mesure que la matrice grandit. En d’autres termes, ils montrent qu’un problème important est difficile, et ils s’efforcent de montrer qu’une catégorie de problèmes est difficile. Cependant, leurs résultats ne sont valables que pour des formulations avec des structures multilinéaires simples et collectives.

Leslie Valiant

Augmenter la profondeur d'un polynôme a tendance à faire diminuer sa taille. Au fil du temps, les informaticiens ont précisé l’arbitrage entre ces deux propriétés. Ils montrent qu’en ajoutant deux niveaux de profondeur à la profondeur 3, les polynômes multilinéaires d’ensemble peuvent équilibrer le gain de taille de leur structure multilinéaire d’ensemble. Si les formules structurées de profondeur 5 prennent un temps exponentiel, il en va de même pour les formules de profondeur 3 de nature générale et non structurée.

De nouveaux travaux de Srikanth Srinivasan et al. montrent que les formulations multilinéaires profondes en 5 ensembles de problèmes de multiplication matricielle croissent effectivement à un rythme exponentiel. Cela signifie que la formule générale de profondeur 3 prend également un temps exponentiel. Ils ont ensuite montré qu’une tendance similaire était valable pour toutes les profondeurs (pas seulement 3 et 5). Avec cette relation, ils ont montré que la taille d’une formule générale de toute profondeur pour le même problème croît de façon exponentielle avec la taille du problème.

Ils montrent également qu'il est difficile d'exprimer la multiplication matricielle dans une formule à profondeur constante, quelle que soit cette profondeur.

Les résultats de cette étude fournissent la première compréhension générale du moment où un problème arithmétique est « difficile » - lorsqu'il ne peut pas être exprimé dans une formule à profondeur constante. Le problème spécifique de la multiplication matricielle est connu sous le nom de problème VP. Et on sait que le problème VP est relativement simple lorsqu'il n'est pas limité à une profondeur constante, il s'avère donc que la profondeur constante est la source de la « difficulté » du problème.

Les problèmes VNP sont-ils plus difficiles que les problèmes VP ? Les nouveaux résultats n’illustrent pas directement cela, ils montrent seulement que la formule de profondeur constante est difficile. Mais cela reste une étape importante pour prouver que le problème VNP ne peut pas être équivalent au problème VP.

Pour le problème plus vaste P vs NP, nous pouvons désormais être plus optimistes que la réponse sera un jour trouvée. Après tout, pour résoudre des problèmes difficiles, nous devons d’abord savoir quelles directions sont désespérées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!