Résultats de physique dans TCS?

Il semble clair qu'un certain nombre de sous-domaines de l'informatique théorique ont été fortement influencés par les résultats de la physique théorique. Deux exemples de ceci sont

1. Calcul quantique
2. Résultats de la mécanique statistique utilisés dans l'analyse de complexité / les algorithmes heuristiques.

Donc, ma question est la suivante: y at-il des domaines importants qui me manquent?

Ma motivation est très simple: je suis un physicien théoricien qui est venu au TCS via des informations quantiques et je suis curieux de connaître d’autres domaines dans lesquels les deux domaines se chevauchent.

C'est une question relativement douce, mais je ne veux pas dire que ce soit une question de type liste volumineuse. Je cherche des domaines où le chevauchement est important.

La technique de recherche simulée recuit est inspirée par le processus physique de recuit en métallurgie.

Le recuit est un traitement thermique dans lequel la force et la dureté de la substance traitée peuvent changer de façon spectaculaire. Cela implique souvent de chauffer la substance à une température extrême, puis de la laisser refroidir lentement.

Le recuit simulé évite les minima / maxima locaux dans les espaces de recherche en intégrant un degré de caractère aléatoire (la température) dans le processus de recherche. Au fur et à mesure que le processus de recherche progresse, la température diminue progressivement, ce qui signifie que la quantité de caractère aléatoire dans la recherche diminue. Apparemment, c'est une technique de recherche assez efficace.

Dans l’inverse (du TCS à la physique), les états de produits matriciels, PEPS (états de paires enchevêtrés projetés), MERA (renaissance de multiniveaux enchevêtrement ansatz) ont été considérablement éclairés par les idées du TCS qui ont été adaptées à la théorie de l’information quantique. Ces acronymes sont toutes des techniques permettant d'approcher les états des systèmes de spin quantiques utilisés par les théoriciens de la matière condensée. Dans de nombreux cas, ces techniques semblent mieux fonctionner que tous les outils connus jusqu'à présent.

Les systèmes complexes sont un domaine qui a beaucoup à voir avec l'analyse des réseaux sociaux et les réseaux en général. Il a été envahi par de nombreux physiciens, brandissant des armes issues de la statistique et de la thermodynamique. Que ce soit envahi par la physique est une autre histoire.

Un résultat de Pour-El et Richards Adv. Math. 39 215 (1981) donne l'existence de solutions non calculables à l'équation d'onde 3D pour les conditions initiales calculables en utilisant cette onde pour simuler une machine de Turing universelle.

La connexion va aussi dans l'autre sens. Il y a quelque temps, des informaticiens théoriciens travaillant dans la théorie des domaines se sont intéressés à la relativité. Ils ont montré des résultats sur la manière de reconstruire la structure de l'espace-temps à partir de la structure de causalité. C’est quelque chose de très familier aux théoriciens du domaine, où les objets d’intérêt beasiques sont des ordres partiels dont la topologie est déterminée par l’ordre. Vous pouvez consulter http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf

Un très vieil exemple (qui pourrait être repris par la réponse de Suresh, mais c’est une approche différente) est l’influence de la théorie des réseaux électriques, par exemple les lois de circuit de Kirchhoff, sur la combinatoire, la théorie des graphes et la probabilité.

Un domaine qui a connu quelques applications, mais pas assez, à l’OMI, est l’approximation de structures ou de processus discrets avec des approximations analytiques. C'est une grosse affaire en mathématiques (par exemple, la théorie analytique des nombres) et en physique (toute la mécanique statistique), mais ne s'est pas révélée aussi populaire en CS pour une raison quelconque.

Une application célèbre de ceci était dans la conception de la Connection Machine. C'était une machine massivement parallèle et, dans le cadre de sa conception, ils devaient déterminer la taille des tampons dans le routeur. Feynman a modélisé le routeur avec des PDE et montré que les tampons pouvaient être plus petits que les arguments inductifs traditionnels. Danny Hillis raconte l'histoire de cet essai .

Théorie de jauge pour les approximations heuristiques de la programmation en nombres entiers (quelques-uns des articles de Misha Chertkov ). Méthodes de groupe de renormalisation pour le comptage combinatoire, chapitres 10 à 12 de "Eléments de la marche aléatoire" de Rudnick / Gaspari. Application de la décomposition intégrale du chemin de Feymann (c.-à-d. Section 9.5.1) à la comptabilisation des promenades évitantes. Pour la connexion au TCS, notez que le régime de traçabilité pour le comptage approximatif sur les graphiques dépend du taux de croissance des allées évitables.

La physique statistique a donné aux informaticiens une nouvelle façon de regarder la SAT, comme indiqué ici . L'idée est que, lorsque le rapport entre les clauses et les variables impliquées dans une formule 3-SAT augmente d'environ 4 à environ 5, nous passons de la résolution de la grande majorité des instances 3-SAT à la possibilité d'en résoudre très peu. Cette transition est considérée comme un "changement de phase" dans SAT.

Cette idée a acquis une notoriété particulière l'été dernier grâce au prétendu article P vs. NP de Deolalikar.

La théorie des systèmes distribués précocement, en particulier les articles de Leslie Lamport et al., A eu un impact sur la relativité restreinte pour obtenir l'image correcte d'un accord (tolérant aux pannes) sur un état du système global. Voir entrée 27. ( Heure, horloges et classement des événements dans un système distribué , communications de l'ACM 21, 7 (juillet 1978), 558-565) dans les Écrits de Leslie Lamport , où Lamport donne les informations générales suivantes sur son papier:

L’origine de cet article a été une note intitulée «Maintenance des bases de données en double» de Paul Johnson et Bob Thomas. Je crois que leur note a introduit l’idée d’utiliser des horodatages de messages dans un algorithme distribué. J'ai une solide compréhension viscérale de la relativité restreinte (voir [5]). Cela m'a permis de saisir immédiatement l'essence de ce qu'ils essayaient de faire. La relativité restreinte nous enseigne qu’il n’existe pas d’ordre invariant des événements dans l’espace-temps; différents observateurs peuvent ne pas être d’accord sur l’un des deux événements survenus en premier. Il n'y a qu'un ordre partiel dans lequel un événement e1 précède un événement e2 si et seulement si e1 peut affecter de manière causale e2. J'ai réalisé que l'essence de Johnson et Thomas L'algorithme s consistait à utiliser des horodatages pour fournir un classement total des événements conforme à l'ordre causal. Cette réalisation a peut-être été brillante. Après l'avoir réalisé, tout le reste était trivial. Parce que Thomas et Johnson n’ont pas compris exactement ce qu’ils faisaient, ils n’ont pas bien compris l’algorithme; leur algorithme permettait un comportement anormal qui violait essentiellement la causalité. J'ai rapidement écrit une petite note le soulignant et corrigeant l'algorithme.

J'ai étoffé cette réponse avec une réponse détaillée sur MathOverflow à la question du wiki de la communauté de Gil Kalai: "Qu'est-ce qu'un livre que vous aimeriez écrire ?"

La réponse élargie cherche à relier les problèmes fondamentaux du TCS et du QIT aux problèmes pratiques de la médecine de guérison et de la médecine régénérative.

• La géométrie de Joseph M. Landsberg et la complexité de la multiplication matricielle (2008)

• La théorie symplectique d' Alvaro Pelayo et de San Vu Ngoc sur des systèmes hamiltoniens complètement intégrables

L’arène mathématique de l’enquête de Landsberg est constituée de variétés sécantes de variétés de Segre , alors que l’arène pour l’enquête de Pelayo et de Ngoc est une variété symplectique à quatre dimensions… il faut un certain temps pour comprendre que ces deux arènes sont des états de produits matriciels, vus respectivement d’un point de vue informatique. (Landsburg) et une perspective géométrique (Palayo et Ngoc). De plus, Palayo et Ngoc ont inclus dans leur enquête une discussion de Babelon, Cantini et Douçot sur une étude semi-classique du modèle de Jaynes – Cummings (notant que le modèle de Jaynes – Cummings est souvent utilisé dans la littérature sur la physique de la matière condensée et l'informatique quantique). ).

Chacune de ces références va loin pour éclairer les autres. En particulier, dans nos propres calculs dynamiques de spin (très pratiques), il a été utile de comprendre que les espaces d’états quantiques décrits de manière variée dans la littérature sous forme d’états de réseaux tenseurs, d’états de produits matriciels et de variétés sécantes de Segre sont richement dotés. avec des singularités dont la structure algébrique, symplectique et riemannienne est actuellement très incomplètement comprise (comme le montrent les revues Pelayo et Ngoc).

Pour nos besoins en ingénierie, l’ approche Landsburg / géométrie algébrique , dans laquelle l’espace-état de la dynamique quantique est considérée comme une variété algébrique plutôt qu’un espace vectoriel, est en train de devenir la plus mathématiquement naturelle. Cela nous surprend, mais, comme de nombreux chercheurs, nous constatons que l’ensemble des outils de la géométrie algébrique est extrêmement efficace pour valider et accélérer les simulations quantiques pratiques.

Les simulationnistes quantiques apprécient actuellement le fait étonnant que de grandes simulations numériques quantiques donnent souvent de bien meilleurs résultats que nous ne pouvons en attendre aucune raison connue. Au fur et à mesure que mathématiciens et physiciens parviennent à une compréhension commune, cet étonnement diminuera certainement et le plaisir restera sûrement. Bien! :)

Les algorithmes de dessin graphique basés sur la force en sont un autre exemple. L'idée est de considérer chaque arête comme un ressort et la disposition des nœuds du graphe correspond à la recherche d'un équilibre dans la collection de ressorts.

Une grande partie des calculs que nous utilisons ont été inventés à l'origine pour résoudre des problèmes de physique. Les exemples incluent le calcul (gravité newtonienne) et la série de Fourier (équation de la chaleur).

Un article récent établit le lien entre Computer Security et le 2e responsable de la thermodynamique.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166

Le concept de potentiel est lié à de nombreux domaines de la physique. Dans cs, le potentiel est utilisé dans l'analyse amortie des structures de données. Nous pouvons examiner comment chaque étape affecte l'entropie du système et obtenir ainsi un coût moyen (amorti) d'une opération avec une structure de données donnée. Cela a donné lieu à de nombreuses structures de données théoriquement meilleures, comme le tas de fibonacci.

ajouter / combler certaines lacunes dans les excellentes réponses / couvertures actuelles - il semble exister un lien étroit entre le TCS et la thermodynamique de diverses manières qui n’a pas encore été complètement exploré, mais qui constitue les frontières de la recherche active. il existe un point de transition associé à SAT, mais il semble également y avoir des points de transition associés à d'autres classes de complexité (voire à toutes). le point de transition SAT est associé à une différence entre les instances "facile" (P) et "dure" (NP), mais toutes les limites de classe de complexité doivent aboutir à la même propriété de type point de transition.

considérez une machine de Turing. il mesure déjà son fonctionnement dans les dimensions normalement physiques du "temps" et de "l'espace". mais notez que cela fait apparemment aussi une unité de "travail" en se déplaçant de carré en carré et en effectuant une transition. en physique l'unité de travail est Joules, qui est aussi une mesure de l'énergie. il semble donc que les classes de complexité ont une relation avec les niveaux d'énergie, les limites ou les régimes.

La théorie de la mécanique quantique voit de plus en plus l'espace et le temps lui-même, l'univers, comme une sorte de système informatique. il semble qu'il possède des "unités de calcul minimales" intrinsèques à sa nature, probablement liées à la longueur de la planche. de sorte que l’examen des problèmes minimaux de Turing pour des machines implique également et concerne également des systèmes physiques / énergétiques minimaux ou même des volumes d’espace requis. [3]

de plus, le concept clé de l' entropie apparaît à plusieurs reprises dans les systèmes TCS et en physique / thermodynamique et peut constituer un principe unificateur pour lequel des recherches encore plus actives révèlent sa nature sous-jacente. [1,2]

[1] entropie en théorie de l'information , wikipedia

[2] quelle est la définition CS de l'entropie , stackoverflow

[3] Quel est le volume d'informations? tcs.se