Chaos et

Je suis intéressé à apprendre les connexions entre le «chaos» ou, plus largement, les systèmes dynamiques et la question . Voici un exemple du type de littérature que je recherche:$P{=}NP$

Ercsey-Ravasz, Mária et Zoltán Toroczkai. "La dureté d'optimisation comme chaos transitoire dans une approche analogique de la satisfaction des contraintes." Nature Physics 7, no. 12 (2011): 966-970. ( Lien du journal .)

Quelqu'un a-t-il écrit une enquête ou fait un recueil bibliographique?

l'article que vous citez par Ercsey-Ravasz, Toroczkaiest très transversal; il s'intègre à / touche plusieurs lignes de recherche complète de problèmes / complexité / dureté NP. la connexion à la physique statistique et aux verres de spin a été découverte principalement via des «transitions de phase» au milieu des années 1990 et cela a conduit à un grand nombre de travaux, voir Gogioso [1] pour une enquête 56p. la transition de phase coïncide avec ce qui est connu comme "le bord du couteau de contrainte" dans [2]. le même point de transition exact apparaît dans des analyses très théoriques de la complexité / dureté du calcul, par exemple [3] qui se rapportent également aux premières études du comportement des points de transition dans les problèmes de clique par Erdos. [4] est une enquête / conférence vidéo sur les transitions de phase et la complexité de calcul par Moshe Vardi. [5] [6] sont des aperçus du comportement de transition de phase à travers des problèmes complets de NP par Moore, Walsh.

puis il y a une étude dispersée mais peut-être croissante des diverses connexions des systèmes dynamiques avec la complexité et la dureté de calcul dans une variété de contextes. il existe un lien général trouvé dans [7], expliquant peut-être certaines des raisons sous-jacentes des fréquents «chevauchements». Les références [8] [9] [10] [11] sont diverses mais montrent un thème récurrent / une apparence transversale entre des problèmes complets de NP et divers systèmes dynamiques. dans ces articles, il y a quelques concepts / exemples de lien hybride entre des systèmes discrets et continus.

le comportement chaotique dans les systèmes complets NP est analysé dans [11].

Une référence quelque peu similaire à Ercsey-Ravasz / Toroczkai dans le domaine des algorithmes quantiques en ce sens que le système dynamique fonctionne "apparemment" en temps P [12]

Dans cet article, nous étudions une nouvelle approche de l'algorithme quantique qui est une combinaison de l'algorithme quantique ordinaire avec un système dynamique chaotique. Nous considérons le problème de satisfiabilité comme un exemple de problèmes NP-complets et soutenons que le problème, en principe, peut être résolu en temps polynomial en utilisant notre nouvel algorithme quantique.

[1] Aspects de la physique statistique dans la complexité computationnelle / Gogioso

[2] Le tranchant du couteau de contrainte / Toby Walsh

[3] La complexité monotone de k-Clique sur des graphes aléatoires / Rossman

[4] Transitions de phase et complexité de calcul / Moshe Vardi

[5] Transitions de phase dans des problèmes NP-complets: un défi pour la probabilité, la combinatoire et l'informatique / Moore

[6] Comportement de transition de phase / Walsh

[7] La détermination des équations dynamiques est difficile / Cubitt, Eisert, Wolf

[8] Le problème du système d'état stationnaire est NP-difficile même pour les systèmes dynamiques booléens quadratiques monotones / Just

[9] Problèmes d'existence de prédécesseur et de permutation pour les systèmes dynamiques séquentiels / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (passe également par Problèmes d'analyse pour les systèmes dynamiques graphiques: une approche unifiée à travers les prédicats de graphes )

[10] Une approche des systèmes dynamiques pour la correspondance des graphiques pondérés / Zavlanos, Pappas

[11] Sur le comportement chaotique de certains problèmes np-complete / Perl

[12] Nouvel algorithme quantique pour l'étude de problèmes NP-complets / Ohya, Volovich

Il existe une tendance de recherche relativement récente (une quinzaine d'années) de mélange de la physique statistique des systèmes désordonnés et des problèmes d'optimisation discrets et combinatoires. Le lien passe par les probabilités de Boltzmann, et la dureté de calcul est liée à la multiplication des états métastables du système physique. Les modèles de verres de spin sont prouvés isomorphes à la plupart des problèmes d'optimisation discrets.

Je vous conseille de commencer par cette thèse, vous y trouverez plus de références

Lenka Zdeborová. Physique statistique des problèmes d'optimisation matérielle sur http://arxiv.org/abs/0806.4112

Un article classique qui, pour être sincère, je ne le comprends pas bien est:

David L. Donoho, Jared Tanner. Universalité observée des transitions de phase dans la géométrie à haute dimension, avec des implications pour l'analyse moderne des données et le traitement du signal à http://arxiv.org/abs/0906.2530

De plus, sur les verres spin, une introduction

Tommaso Castellani, Andrea Cavagna. Théorie du verre tourné pour les piétons

Malheureusement, il est derrière un mur payant, donc je ne peux pas voir ce document, mais à la lecture du résumé, il présente au moins une similitude superficielle avec certaines "images de dessins animés" que j'ai vues sur la propagation de l'enquête et il est utilisé pour résoudre 3-SAT. Voici une "image de dessin animé" de "Un nouveau regard sur la propagation de l'enquête et ses généralisations" de Maneva, Mossel et Wainwright.

$\alpha_d$$\alpha_c$$\approx 4.2$

Il serait intéressant de voir si les emplacements des différentes régions fractales signalés par Ercsey-Ravasz et Toroczkai correspondent aux différents seuils critiques observés dans la propagation de l'enquête (ou si je me trompe complètement et que la similitude est vraiment superficielle).

Cet article, Solution en temps polynomial de factorisation principale et de problèmes NP-complets avec des machines numériques de calcul numérique, revendique un algorithme efficace pour les problèmes NP-complets. Les machines numériques de memcomputing sont des systèmes dynamiques non linéaires conçus pour que leurs points d'équilibre correspondent aux solutions d'un problème de satisfaction booléen. L'implication la plus importante est qu'un système dynamique qui résout efficacement les problèmes NP-complets peut exister. Ils concluent que leur résultat ne résout pas encore le problème P vs NP. P = NP découlerait de la preuve formelle que si des équilibres existent, l'attracteur global ne supporte pas les orbites périodiques et / ou les attracteurs étranges.

Référence:

1- Traversa et Di Ventra, Solution en temps polynomial de la factorisation principale et des problèmes NP-complets avec les machines numériques de calcul numérique , Chaos: An Interdisciplinary Journal of Nonlinear Science, Volume 27, Issue 2, 2017

2- Traversa, Ramella, Bonani et Di Ventra, Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states , Science Advances, Volume 1, Issue 6, 2015.