De bons exemples de «deux, c'est facile, trois, c'est difficile» en sciences informatiques

29

J'ai récemment rencontré une formulation du méta-phénomène : " deux c'est facile, trois c'est dur " (formulé de cette façon par Federico Poloni), qui peut être décrit comme suit:

Lorsqu'un certain problème est formulé pour deux entités, il est relativement facile à résoudre; cependant, un algorithme pour une formulation à trois entités augmente énormément la difficulté, ce qui peut même rendre la solution impossible ou impossible à atteindre.

(J'accueille favorablement les suggestions pour rendre le phrasé plus beau, concis et précis.)

Quels bons exemples dans divers domaines des sciences informatiques (à partir de l'algèbre linéaire pure et se terminant par une physique numérique à terme générique) connaissez-vous?

Anton Menshov
la source
2
La malédiction de la dimensionnalité vient à l'esprit.
Paul
4
graphique 2-coloration ( facile ) contre 3-coloration ( NP-difficile ), voir ici
GoHokies
5
@GoHokies Veuillez ne pas poster de réponses sous forme de commentaires.
David Richerby
4
De la base de fond mathématique ou récursif, vous pourriez rencontrer la fonction TREE , où TREE (2) = 3, et TREE (3) est ... assez grand. (ne connaissant pas les sciences informatiques, je ne suis pas sûr que ce soit vraiment une réponse que vous recherchez, mais elle semble suffisamment similaire pour laisser un commentaire)
BurnsBA
2
Un contre-exemple: "Ne partez jamais en mer avec deux chronomètres, prenez-en un ou trois." Cela dit, il y a tellement de bons exemples qu'il n'y a pas de bonne réponse. Cette question devrait être un wiki communautaire.
David Hammen

Réponses:

35

Un exemple qui apparaît dans de nombreux domaines de la physique, et en particulier la mécanique classique et la physique quantique, est le problème des deux corps. Le problème des deux corps signifie ici la tâche de calculer la dynamique de deux particules en interaction qui, par exemple, interagissent par des forces gravitationnelles ou coulombiennes. La solution à ce problème peut souvent être trouvée sous forme fermée par une transformation variable en centre de masse et coordonnées relatives.

Cependant, dès que l'on considère trois particules, en général aucune solution sous forme fermée n'existe .

davidhigh
la source
3
Nitpick que je suis sûr que vous connaissez, mais votre réponse ne dit pas: Il existe des solutions sous forme fermée au problème des 3 corps, mais seulement pour quelques cas spéciaux
lama
bon nitpick, merci, "en général" manque ici.
davidhigh
Notez que le problème à 3 corps a une solution en série ( convergeant très lentement) trouvée par Sundman au début du 20e siècle et une version plus faible (qui ignore les singularités où les corps entrent en collision) a été trouvée pour le problème à n corps en 1990.
WorldSEnder
27

Un exemple célèbre est le problème de satisfiabilité booléenne (SAT). 2-SAT n'est pas compliqué à résoudre en temps polynomial, mais 3-SAT est NP-complet.

Federico Poloni
la source
3
3-SAT peut être réduit en graphique 3-coloration, ou vice-versa
GoHokies
8
@GoHokies Je pensais que c'était vrai pour chaque problème np-complet? Ou est quelque chose de particulièrement remarquable à propos de ces deux? Sry si c'est une question stupide, mes connaissances dans ce domaine sont basiques. Mais c'est ainsi que je comprends le théorème des cuisiniers
findusl
2
@findusl Vous avez parfaitement raison. Ce qui rend la 3-SAT et la 3-coloration «spéciales» est la dichotomie 2 vs 3 de l'OP.
GoHokies
26

En une et deux dimensions, toutes les routes mènent à Rome, mais pas en trois dimensions.

Plus précisément, étant donné une marche aléatoire (également susceptible de se déplacer dans toutes les directions) sur les nombres entiers dans une ou deux dimensions, alors quel que soit le point de départ, avec une probabilité une (aka presque sûrement), la marche aléatoire finira par arriver à une destination spécifique désignée point ("Rome").

Cependant, pour trois dimensions ou plus, la probabilité d'arriver à "Rome" est inférieure à un; avec une probabilité décroissante à mesure que le nombre de dimensions augmente.

Ainsi, par exemple, si vous effectuez une simulation stochastique (Monte Carlo) d'une marche aléatoire à partir de "Rome", qui s'arrêtera lorsque Rome sera de retour, puis en une et deux dimensions, vous pouvez être assuré de revenir éventuellement à Rome et arrêter la simulation - si facile. En trois dimensions, vous ne pourrez jamais revenir en arrière, si dur.

https://en.wikipedia.org/wiki/Random_walk#Higher_dimensions

Pour visualiser le cas bidimensionnel, on peut imaginer une personne marchant au hasard dans une ville. La ville est effectivement infinie et disposée en une grille carrée de trottoirs. À chaque intersection, la personne choisit au hasard l'un des quatre itinéraires possibles (y compris celui à l'origine emprunté). Formellement, il s'agit d'une marche aléatoire sur l'ensemble de tous les points du plan avec des coordonnées entières.

La personne reviendra-t-elle jamais au point de départ initial de la marche? C'est l'équivalent bidimensionnel du problème de passage à niveau discuté ci-dessus. En 1921, George Pólya a prouvé que la personne ferait presque sûrement une marche aléatoire en 2 dimensions, mais pour 3 dimensions ou plus, la probabilité de revenir à l'origine diminue à mesure que le nombre de dimensions augmente. En 3 dimensions, la probabilité diminue à environ 34%

Voir http://mathworld.wolfram.com/PolyasRandomWalkConstants.html pour les valeurs numériques.

Mark L. Stone
la source
21

En voici une qui tient à cœur aux contributeurs de SciComp.SE:

Le problème d' existence et de douceur de Navier – Stokes

La version tridimensionnelle est bien sûr un problème ouvert célèbre et fait l'objet d'un prix Clay Millenium d'un million de dollars. Mais la version bidimensionnelle a déjà été résolue il y a longtemps, avec une réponse affirmative. Terry Tao note que la solution remonte essentiellement à la thèse de Leray en 1933!

Pourquoi le problème tridimensionnel est-il tellement plus difficile à résoudre? La réponse standard, ondulée à la main, est que la turbulence devient beaucoup plus instable en trois dimensions qu'en deux. Pour une réponse mathématiquement plus rigoureuse, consultez l'énoncé officiel du problème de Charles Fefferman au Clay Institute ou la belle exposition de Terry Tao sur les stratégies de preuve possibles .

Richard Zhang
la source
20

Dans la théorie du choix social, la conception d'un système électoral avec deux candidats est facile (règles de la majorité), mais la conception d'un système électoral avec trois candidats ou plus implique nécessairement de faire des compromis entre diverses conditions raisonnables. ( Théorème d'impossibilité de Arrow ).

ajd
la source
11

Diagonalisation simultanée de deux matrices A1 et A2 :

U1TA1V=Σ1,U2TA2V=Σ2
est couvert par ladécompositionexistantedes valeurs singulières généralisées.

Cependant, lorsque la réduction simultanée de trois matrices à une forme canonique (condition plus faible par rapport à ce qui précède) est requise:

QTA1Z=A1~,QTA2Z=A2~,QTA3Z=A3~
aucune méthode directe n'existe. Pour cela, il faut opter pour des itinéraires plus compliqués en utilisant des SVD approximatifs, des décompositions de tenseurs, etc.

Une application pratique serait une solution à un problème de valeur propre quadratique:

(A1+λA2+λ2A3)x=0

Source: CF van Loan, «Conférence 6: La décomposition généralisée des valeurs singulières d'ordre supérieur», Université d'été CIME-EMS, Cetraro, Italie, juin 2015.

Anton Menshov
la source
Faut - et U T 2 à la fois être V - 1 ? Ici, ils ne sont même pas tenus d'être égaux. U1TU2TV1
Rosie F
1
Σ
9

Il existe de nombreux exemples en informatique quantique, bien que je sois hors de ce sujet depuis un certain temps et que je ne m'en souviens donc pas. L'un des principaux est que l'intrication bipartite (enchevêtrement entre deux systèmes) est relativement facile, tandis que l'intrication entre trois systèmes ou plus est un gâchis non résolu avec probablement une centaine d'articles écrits sur le sujet.

max(uavbwcTabc/uvw)

Ce document semble pertinent, bien que je ne l'ai pas lu: la plupart des problèmes de tenseur sont NP-difficiles

Dan Stahlke
la source
2
Je pense que le vrai problème que vous rencontrez est que la décomposition du rang de tenseur est facile pour les tenseurs d'ordre 1 (vecteurs) et les tenseurs d'ordre 2 (matrices), mais NP-difficile pour le reste
Richard Zhang
Cela en fait partie, mais même si vous aviez un moyen de les décomposer, il y a toujours le problème de la catégorisation / classification. Pour l'intrication, les unités locales n'ont pas d'importance, donc tout ce qui reste dans le cas d'ordre 2 est une liste de valeurs singulières (SVD est appelé décomposition de Schmidt dans ce contexte). Pour les commandes supérieures, il y a tout un zoo de possibilités. La question de savoir quels états peuvent être transformés en d'autres états via des opérations locales finit par être très difficile (d'un point de vue théorique, pas nécessairement informatique).
Dan Stahlke
5

La bissection d'angle avec règle et boussole est simple, la trisection d'angle est en général impossible.

davidhigh
la source
4

Inférence de type pour les types de rang n . L'inférence de type pour le rang 2 n'est pas particulièrement difficile, mais l'inférence de type pour le rang 3 ou supérieur est indécidable.

André Popovitch
la source
4

Voici une bonne idée de l'optimisation: l'algorithme ADMM (Alternating Direction Method of Multipliers).

Étant donné une fonction objective non couplée et convexe de deux variables (les variables elles-mêmes pourraient être des vecteurs) et une contrainte linéaire couplant les deux variables:

minf1(x1)+f2(x2)
s.t.A1x1+A2x2=b

Lρ(x1,x2,λ)=f1(x1)+f2(x2)+λT(A1x1+A2x2b)+ρ2||A1x1+A2x2b||22

Lρ(x1,x2,λ)x1x2,λLρ(x1,x2,λ)x2x1,λλ. Ce cycle se poursuit jusqu'à ce qu'un critère d'arrêt soit atteint.

(Remarque: certains chercheurs comme Eckstein rejettent la vue de fractionnement de Gauss-Siedel en faveur des opérateurs proximaux, par exemple voir http://rutcor.rutgers.edu/pub/rrr/reports2012/32_2012.pdf )

Pour les problèmes convexes, il a été prouvé que cet algorithme converge - pour deux ensembles de variables. Ce n'est pas le cas pour trois variables. Par exemple, le problème d'optimisation

minf1(x1)+f2(x2)+f3(x3)
s.t.A1x1+A2x2+A3x3=b

fxiλ

https://web.stanford.edu/~yyye/ADMM-final.pdf

Nathaniel Kroeger
la source
3

Plier un morceau de papier en deux sans outils est facile. Le plier en tiers est difficile.

La factorisation d'un polynôme à deux racines est facile. La factorisation d'un polynôme à trois racines est beaucoup plus compliquée.

Lupus arcaniste
la source
3
Votre premier exemple ne correspond pas à l'esprit de la citation. L'idée est qu'à mesure qu'elle monte au-delà des deux, c'est plus difficile, mais avec le pliage d'un papier, les 4èmes sont à peu près aussi faciles que la moitié. La citation ici serait "Même est plus facile que bizarre", je pense que le second est bon - et 'grats d'essayer de l'hyper-simplifier avec le papier!
Bill K
3

f(x,y)=0f

Cette différence a plusieurs implications:

  • Au degré 2, il existe des algorithmes pour trouver tous les points rationnels (solutions en nombres rationnels), au degré 3 aucun algorithme de ce type n'est connu.
  • f(x)ff
  • Le problème du logarithme discret est traitable sur des courbes de degré 2, donc ne convient pas aux applications cryptographiques, tandis que la dureté supposée du même problème sur les courbes elliptiques est à la base de certains des cryptosystèmes à clé publique les plus populaires.
doetoe
la source
1

La TREEfonction.

Nous pouvons calculer TREE(2) = 3, mais TREE(3)n'est pas calculable dans la vie de l'univers, nous savons seulement qu'il est fini.

juste la moitié
la source
TREE(3)nn
D'accord, désolé pour l'erreur. Correction de ma déclaration. Merci Solomonoff!
juste la moitié
1
Vidéo numérophile associée sur Tree (3): youtube.com/watch?v=3P6DWAwwViU
Novice C
1

Dans un espace à deux dimensions, vous pouvez introduire une structure complexe, qui peut être utilisée pour résoudre avec élégance de nombreux problèmes (par exemple, des problèmes d'écoulement potentiels ), mais aucun analogue n'existe en 3 dimensions.

Patrick Sanan
la source
0

En physique quantique à plusieurs corps, nous étudions différents réseaux de n spins dans le cadre de différents modèles (par exemple modèle Heisenberg, modèle Bose-Hubbard, modèle Ising, ...). Vous avez bien sûr différentes méthodes numériques pour les étudier (DMRG, diagonalisation exacte, réseaux de neurones, ...) et l'une des raisons pour lesquelles nous essayons de développer différentes méthodes est que vous ne pouvez pas résoudre ces modèles lorsque n devient trop "élevé" , et c'est bien sûr pire si vous étudiez dans des dimensions plus élevées. Par exemple, pour le modèle d'Ising, la diagonalisation exacte fonctionne bien en 1d pour n non supérieur à 20. Donc, pour n plus élevé, vous essayez une autre méthode: DMRG. Mais ces derniers fonctionnent bien pour n plus élevé (comme n = 70 mais pas bien pour n supérieur). Encore une fois, vous voulez une autre méthode pour les réseaux de neurones n supérieurs (c'est-à-dire l'intelligence artificielle). Et en plus des réseaux de neurones, vous pouvez étudier "plus facilement" (c'est-à-dire avec un n relativement plus élevé) ces modèles dans des dimensions plus élevées (mais pour la dimension = 3 et le petit n, par exemple, il faut encore beaucoup d'heures (plusieurs jours) pour obtenir l'état fondamental ou observable que vous vouliez ...). Bref, quand n devient "trop ​​élevé" pour vos méthodes numériques (mais aussi la capacité de votre ordinateur) vous devez effectuer de nouvelles méthodes (et si vous le pouvez, utiliser un super ordinateur) et c'est le même problème avec la dimension de votre système mais pire bien sûr car vous êtes rapidement coincé (dimension = 4 est difficile à obtenir sauf si vous attendez beaucoup de temps ...). il faut encore beaucoup d'heures (plusieurs jours) pour obtenir l'état fondamental ou l'observable que vous vouliez ...). Bref, quand n devient "trop ​​élevé" pour vos méthodes numériques (mais aussi la capacité de votre ordinateur) vous devez effectuer de nouvelles méthodes (et si vous le pouvez, utiliser un super ordinateur) et c'est le même problème avec la dimension de votre système mais pire bien sûr car vous êtes rapidement coincé (dimension = 4 est difficile à obtenir sauf si vous attendez beaucoup de temps ...). il faut encore beaucoup d'heures (plusieurs jours) pour obtenir l'état fondamental ou l'observable que vous vouliez ...). Bref, quand n devient "trop ​​élevé" pour vos méthodes numériques (mais aussi la capacité de votre ordinateur) vous devez effectuer de nouvelles méthodes (et si vous le pouvez, utiliser un super ordinateur) et c'est le même problème avec la dimension de votre système mais pire bien sûr car vous êtes rapidement coincé (dimension = 4 est difficile à obtenir sauf si vous attendez beaucoup de temps ...).
Bien sûr, ici, ce sont des informations supplémentaires à votre question car en fait, en physique quantique à plusieurs corps, n = 3 n'est pas élevé (mais si vous prenez un réseau qui est un hypercube, vous ne pouvez pas prendre n = 3 de cours (en raison des conditions)).

Albert B.
la source
-3

Monde réel:

Automatisation% - par exemple, il est facile d'automatiser quelque chose à 30%, 50% ou 80%, alors qu'il est difficile d'aller par exemple au-dessus de 95% et incroyablement difficile, voire presque impossible, d'atteindre 100%.

Joelty
la source
2
Pouvez-vous fournir des références pour vos réclamations?
nicoguaro
Je ne peux pas, mais regardez par exemple les voitures autonomes. Apprendre à conduire en ligne droite et à contrôler la vitesse est probablement plus facile que d'apprendre à conduire comme une personne normale. Le processus le plus complexe est, puis plus de cas de frontière apparaissent lorsque vous voulez le rendre entièrement automatisé
Joelty
Ensuite, je pense que votre question n'est pas appropriée pour ce site.
nicoguaro