Résultats de physique dans TCS?

42

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.

Joe Fitzsimons
la source
9
Je ne sais pas si les systèmes complexes comptent, alors je ne réponds pas encore. c'est un domaine qui a beaucoup à voir avec l'analyse des réseaux sociaux et les réseaux en général et qui 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.
Suresh Venkat
Je penserais que ça compte.
Joe Fitzsimons
voir aussi comment sont la physique / CS devient unie physics.se
VZN

Réponses:

26

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.

Dave Clarke
la source
supercooldave: Ma compréhension limitée était que le recuit simulé évite seulement les minima locaux qui sont "suffisamment superficiels". Est-ce exact?
Joshua Grochow
1
@ Josué: en général, le recuit simulé ne permet pas toujours d'éviter le minimum local. Il peut toujours rester bloqué au mauvais endroit. Quelques expériences sont nécessaires pour trouver un bon point de départ, etc.
Dave Clarke
1
Bien sûr, il convient de noter que le «véritable» recuit n'évite pas toujours les minima locaux non plus! Les défauts (au sens mathématique-physique) ne sont pas inconnus.
Steven Stadnicki
Si la baisse de température se fait de manière exponentielle lente, le recuit simulé acquiert de nombreuses propriétés d'optimisation globales souhaitables. Bien sûr, il gagne également un temps d'exécution exponentiel.
Elliot JJ
23

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.

Peter Shor
la source
2
Ce qui me frappe dans ce domaine, c’est qu’il semble que c’est plus la communauté de la physique théorique au sein de l’information quantique que la communauté du SDC (si nous pouvons vraiment faire une telle distinction) qui semble s'intéresser à ces techniques.
Joe Fitzsimons
5
Je serais certainement d'accord. J'ai essayé de faire en sorte qu'un étudiant de deuxième cycle s'y intéresse très tôt, mais sa réaction a été "bien… ce ne sont que des méthodes d'approximation heuristique, et vous ne pouvez rien dire de rigoureux à leur sujet." Bien sûr, cela s'est avéré incorrect.
Peter Shor
1
(@Shor) J'ai beaucoup aimé cette réponse, et j'ai fourni une réponse complémentaire avec plusieurs références supplémentaires - dont au moins une (l'enquête de 2008 de Joseph Landsburg, Géométrie et la complexité de la multiplication matricielle ) est très certainement à la fin du TCS le spectre. cstheory.stackexchange.com/questions/2074/…
John Sidles
20

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.

Suresh Venkat
la source
Je développe un assez fort intérêt pour les réseaux et l'analyse de réseaux sociaux. Avez-vous des références?
Dave Clarke
2
hmm. Le mieux est de commencer par le livre Kleinberg / Easley (qui est un bon texte de premier cycle). Ensuite, vous pouvez travailler d'avant en arrière d'Aaron Clauset et Mark Newman
Suresh Venkat le
19

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.

S Huntsman
la source
Je mentionnerais également l’informatique ADN comme un domaine de chevauchement, même si ses liens avec la physique théorique sont plus ténus.
S Huntsman
Je pensais plutôt aux domaines dans lesquels le SDC avait tiré profit des résultats obtenus en physique, plutôt que l'inverse.
Joe Fitzsimons
7
Eh bien alors (bien que cela puisse être considéré comme implicite dans ou lié à un autre élément mentionné sur cette page), je voudrais négliger de mentionner la théorie du calcul réversible, notamment le cercle d’idées né du travail de Landauer, qui a influencé de nombreux autres domaines autres que l'informatique quantique.
S Huntsman
Pour commenter la réponse de Suresh (pas assez de représentants pour commenter là-bas): il y a eu de nombreuses applications fructueuses des idées en physique à l'analyse de la dynamique des réseaux. À titre d'exemple, je me souviens d'un article traitant des preuves que le trafic TCP manifestait une criticité auto-organisée. Autre exemple, quelques chercheurs (dont moi-même) ont travaillé sur l’application d’idées de la physique (et pas seulement de l’entropie) à la caractérisation du trafic réseau pour la détection d’anomalies. Bien sûr, cela laisse le T sur TCS.
S Huntsman
17

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

Andrej Bauer
la source
3
Oui, en fait, j'ai entendu Prakash en parler à son atelier à la Barbade. Un travail vraiment intéressant. J'avais cependant l'impression qu'il avait également une formation en physique. Cela dit, il y a certainement des contributions dans les deux sens. Il se trouve que j'étais particulièrement intéressé par la découverte d'une direction en particulier. Vraisemblablement, poser des questions sur l’influence du TCS sur la physique conviendrait mieux à un site Web sur la physique, car les spécialistes du domaine qui adaptent les idées d’un deuxième domaine sont mieux placés pour déterminer lesquels ont eu un impact significatif sur le premier.
Joe Fitzsimons
13

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é.

RJK
la source
11

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 .

Neel Krishnaswami
la source
2
Qu'en est-il de la combinatoire analytique (Flajolet et Sedgewick)?
RJK
11

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.

Yaroslav Bulatov
la source
9

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.

Huck Bennett
la source
Ah oui, je viens de me rendre compte que Joe a fait référence à cela dans sa question initiale. Espérons que cela se développe un peu.
Huck Bennett
9

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.

Martin Schwarz
la source
9

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.


Cette réponse complète la réponse de Peter Shor , qui traite des rôles des états de produits matriciels dans le TCS et la physique. Deux enquêtes récentes dans le Bulletin de l'AMS sont pertinentes pour les états du produit matriciel. Les deux enquêtes sont bien rédigées, ne font pas l'objet de restrictions quant au paiement et sont raisonnablement accessibles aux non-spécialistes:

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! :)

John Sidles
la source
8

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.

Dave Clarke
la source
Je n'aurais pas pensé que cela soit particulièrement vrai pour le TCS, mais c'est une technique tellement géniale que vous obtenez un +1 de ma part. Après tout, certains domaines de l'informatique dépendent énormément de la physique (SIGGRAPH).
Joe Fitzsimons
Les graphes sont sûrement TCS. Et ils doivent être tirés. Et David Eppstein dessine des graphiques. (Ceci est mon argument convaincant.)
Dave Clarke
Ok, je vais accepter cet argument.
Joe Fitzsimons
Cette technique est un acteur majeur du dessin graphique. certainement la peine mention
Suresh Venkat
Excellent exemple! +1 de moi
George
2

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).

Warren Schudy
la source
6
Dans la même veine, Belkin, Narayanan et Niyogi (FOCS '06, dx.doi.org/10.1109/FOCS.2006.34 ) ont utilisé une analyse mathématique tirée de l'étude du flux de chaleur et de la diffusion pour donner un algorithme rapide randomisé de calcul de la surface un corps convexe en n dimensions.
arnab
2
bon exemple. Bien que ce soit un exemple de la physique ou des mathématiques? :)
Suresh Venkat
1

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.

Nate
la source
-1

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

vzn
la source
1
Vous vous rendez compte que j'ai répondu à la question tcs.se, non?
Joe Fitzsimons
J'aimerais comprendre pourquoi cette question a été votée. Voter à la baisse sans explication n’aide personne, car les raisons peuvent être non techniques. Je comprends que le PO était au courant de tout ou partie de cette réponse, mais puisqu'il ne l'a pas mentionné dans la question ... cc @JoeFitzsimons
babou