vendredi 29 février 2008

Les théories pré-espace temps

J'ai souhaité écrire cet article pour tenter de faire un petit état des lieux, à mon niveau, des théories qui décrivent la création de l'univers - ou plus précisément ce qui a engendré l'Univers - et discuter les hypothèses qui sous-tendent ces théories.

Vous trouverez aussi dans cet article quelques réflexions subjectives un peu "métaphysiques", j'ai annoté ces passages "Mon point de vue".

Avant toute chose, pour se mettre d'accord sur le vocabulaire, je tenterai de donner une, ou plutôt deux définitions de l'univers.

Définition A (scientifique) : L'Univers est la sphère causale qui englobe toute les ondes, particules et forces physiques

Définition B (sémantique) : L'Univers est l'ensemble de toute chose.

La définition A que j'ai surnommée "scientifique" est celle - me semble t'il - qui est admise par la communauté scientifique.

La définition B est plutôt "sémantique", elle s'intéresse à ce que signifie le mot Univers, indépendamment des connaissances scientifiques actuelles.

Comme je l'ai précisé, les théories pré-Univers proposées au sein de la communauté scientifique portent toutes (à ma connaissance), sur la définition A. La définition B quant à elle paraît plus métaphysique et il semble donc difficile d'élaborer un modèle concret à partir d'une définition aussi vague. Examinons donc les théories pré-Univers compatibles avec la définition A. J'appelerai ces théories Ax, x étant l'ordre dans lequel j'en parle (ayant une très faible connaissance de ces théories, je n'ai aucune préférence particulière)

Une dernière précision : je ne prétend pas donner une explication complète ni même correcte de chaque théorie évoquée ci-dessous, j'essayerai simplement d'en résumer l'idée principale. Toutes les précisions ou corrections seront les bienvenues.

Théorie A1 : Le scénario ekpyrotique

L'Univers ("sphère causale") serait issu du "choc" entre deux membranes à plusieurs dimensions (au sens de la théories des cordes). Ces membranes seraient en mouvement périodique, qui engendrerait un cycle création/destruction de l'Univers, à priori infini.

Théorie A2 : Le scénario du Multivers

L'Univers serait une "bulle" causale, engendré par une autre bulle-Univers causale. Il existerait une infinité (?) d'Univers connectés les uns aux autres dans une sorte d'arbre, que l'on pourrait appeler le Multivers.

Ces deux théories - j'imagine, comme d'autres théories Ax - ont un avantage indéniable : elles permettent de respecter le principe de conservation de l'entropie (énergie/matière). En effet, la sphère causale est vue comme le résultat d'une interaction entre d'autres éléments, dans un système plus grand (les membranes ou le multivers) : rien ne se crée, rien ne se perd, etc.

Cependant en faisant cela, ne retombe t'on pas finalement sur la même question, légèrement transformée : Au lieu de se demander "d'où vient l'Univers ?" on se demande maintenant "d'où viennent les membranes ?" ou "d'où vient le Multivers ?" ...

Je ne connais pas l'explication pour la théorie ekpyrotique, je peux cependant citer l'argument de la théorie du Multivers : Le Multivers représente l'ensemble de tous les Univers possibles, il n'y a donc pas d'explication - ou de choix - à l'origine de son existence. Donc pour revenir à nous, nous existons dans notre Univers car c'est celui dans lequel on existe : il s'agit de l'argument anthropique. J'imagine que la théorie ekpyrotique avance un argument un peu similaire, du style : chaque cycle engendre un Univers différent qui au final créé tous les Univers possibles, on peu alors avancer l'argument anthropique.

Un dernier point commun qui me semble essentiel entre ces 2 théories est l'aspect "infini" du méta-système (membranes ou multivers), par opposition à la taille "finie" de l'Univers (sphère causale).

En outre, ce que j'ai appelé le méta-système (membranes ou multivers) semble correspondre maintenant à la définition B : L'ensemble de toute chose.

Mon point de vue :

Depuis que je suis tout petit, j'adhère à la définition B. Pour moi, l'Univers ne peut-être que l'ensemble de toute chose : si l'on trouve quelque chose qui englobe l'Univers connu, alors on devrait appeler ce nouvel ensemble l'Univers.

J'aimerai au passage donner ma "démonstration" (un peu tirée par les cheveux, il est vrai...) de la non existence de Dieu avec cet argument :

Supposons que Dieu existe et a créé l'Univers. L'Univers étant l'ensemble de toutes chose (B), on en déduit que Dieu est inclus dans l'Univers. Supposons enfin, comme c'est le cas - à ma connaissance - dans les 3 grandes religions monothéistes, que Dieu "est partout", autrement dit que l'Univers est inclus dans Dieu. Ces deux concepts étant inclus l'un dans l'autre, on en déduit qu'il sont égaux : le mot Dieu, désigne la même chose que le mot Univers. On peut penser soit que Dieu n'existe pas, que ce n'est qu'un autre terme pour définir l'Univers, soit que l'Univers est Dieu (pour les plus croyants).

Je tiens à préciser que le point - à mon avis - sur lequel les religieux ne sont pas d'accord avec ce raisonnement est la définition B de l'Univers : L'Univers n'est pas l'ensemble de toute chose, car Dieu n'est pas DANS l'Univers, Dieu l'a créé.

Pour conclure ce point de vue, il semble que "ma" définition de l'Univers ne soit ni acceptée par les scientifiques, ni par les religieux (je suis tout seul ...snif) . Plus étonnant encore, il semble même, d'après la remarque que j'ai faite dans le paragraphe précédent, que la définition A de l'Univers soit la même pour les scientifiques ET pour les religieux (aurions nous trouvé un point d'entente ?)

Je reviendrai dans la prochaine partie sur les théories A1 et A2 et j'essayerai de défendre "ma" définition B en présentant une théorie que j'appellerai - à priori - B1.

A suivre...

lundi 11 février 2008

P = NP : problème ou illusion ? (partie 3)

Dans la deuxième partie , nous avons calculé la complexité de la multiplication scolaire à N chiffres : il s'agit d'un calcul à temps quadratique, nous avions vu que l'addition scolaire est un calcul à temps linéaire dans la première partie

Nous avions conclut que ces deux opérations appartiennent à l'ensemble P, qui représente l'ensemble des calculs déterministes à temps polynomial.

Dans la conjecture P = NP, l'ensemble NP représente les calculs non déterministes à temps polynomial. Mais avant de revenir sur cet ensemble plus en détail, il nous faut voir une dernière notion.

Avant, je dois préciser que certains passages peuvent contenir des erreurs pour deux raisons : d'une part, je ne suis pas un spécialiste de la théorie de la complexité et encore moins du problème P = NP. D'autre part, je présenterai à certains endroits mon point de vue, qui là encore peut contenir des erreurs ou même sembler simpliste aux spécialistes, vous voilà prévenus...

Les calculs à temps exponentiel

Imaginons que l'on souhaite connaître le nombre d'ancêtres A que nous avons, pour une génération N, par exemple :

A(1) = 2 (parents)
A(2) = 4 (grands parents)
A(3) = 8 (arrière grands parents)
...
A(N) = 2^N

Pour calculer A(N), il nous faut multiplier le résultat précédent A(N-1) par deux. En prenant comme opération unitaire la multiplication, on a donc un calcul à temps exponentiel, c'est à dire du type :

T(calcul exponentiel) = K^N

Où K est un nombre fixé (2 dans le cas du calcul des ancêtres) et N le nombre de données (dans notre exemple, le nombre de générations)

Un point fréquent dans les calculs à temps exponentiels est qu'ils sont récursifs : pour calculer A(N), on doit calculer A(N-1). Le résultat final n'est possible qu'en faisant tous les calculs

Mon point de vue : On peut se représenter le calcul à temps polynomial ou exponentiel comme une série de calculs à effectuer dans l'ordre : les calculs sont "branchés" en série, un peu comme des composants d'un circuit électrique. Tous les "circuits sont nécéssaires pour alimenter" le résultat. Les problèmes P ou E (voir plus bas) sont des "calculs en ET".

Nous pouvons maintenant définir l'ensemble E, comme étant l'ensemble des calculs à temps exponentiel. Mais quel rapport avec P = NP ? En quoi cela peut-il nous aider à définir l'ensemble NP ?

Calculs non déterministes à temps polynomial

Que signifie un calcul "non déterministe" ? En gros, que l'algorithme doit effectuer un certain nombre de calculs indépendants les uns des autres et qu'en fonction du "choix" qu'il fera, il pourra mettre moins de temps que nécéssaire, s'il avait dû tous les calculer, ou s'il les avait calculé dans un "ordre déterministe".

Pour cette raison, on dit souvent que les problèmes de la classe NP sont des problèmes de "décision".

On observe plusieurs propriétés importantes des problèmes de la classe NP :
- On peut calculer un problème NP avec un algorithme à temps exponentiel
- On peut vérifier le calcul d'un problème NP avec un algorithme à temps polynomial

On voit qu'en terme d'efficacité, les problèmes NP semblent se situer "entre" les problèmes P et E.

Autre point important : un problème P fait également partie de la classe NP. En termes ensembliste, on dira que l'ensemble P est inclus dans l'ensemble NP.

En mathématique, pour que deux ensembles (P et NP) soient égaux, il faut (et il suffit) qu'ils soient inclus l'un dans l'autre. Nous savons déjà que P est inclus dans NP. Toute la question de l'hypothèse P = NP est en fait de savoir si la réciproque est vraie : En fait la question n'est pas "P est-il égal à NP ?", mais plus précisément "NP est-il inclus dans P ?", autrement dit :

Pour chaque problème NP, existe-il un algorithme déterministe à temps polynomial capable de le résoudre ?

Généralement, les problèmes mathématiques commençant par "Pour chaque...existe t'il..." sont les plus difficiles à résoudre , car il faut démontrer l'existence d'un tel algorithme pour chaque problème, mais comment peut-on étudier en même temps TOUS les problèmes de type NP ? (Une blague de mathématicien serait de dire qu'on se trouve en face d'un problème à temps exponentiel...)

En fait, dans les années 60, un mathématicien américain du nom de Stephen Cook a découvert qu'on pouvait étudier tous les problèmes d'une classe, en étudiant uniquement "les plus difficiles" de cette classe : En résumé, "qui peut le plus, peut le moins". On appelle ces problèmes des problèmes complets.

Un problème NP-Complet : le problème du voyageur

Imaginons qu'un touriste veuille visiter N villes. Il souhaite effectuer le trajet le plus court possible, ou plus précisément, plus court qu'une certaine distance autorisée, qu'on appelera D, tout en passant par toutes les villes.

Pour résoudre ce calcul il faudrait à priori calculer toutes les combinaisons possibles de trajets, soit (N-1)! et sélectionner uniquement celles inférieures à D, par exemple :

Pour deux villes (N=2), il y a 1 seul trajet possible (T=1), donc une seule distance à calculer.

N = 3, T = 2
N = 4, T = 6
N = 5, T = 24
...
N = k, T = (k-1)! = (k-1) * (k-2) * ... * 1

On retrouve un peu le même schéma que pour le calcul des ancêtres (à temps exponentiel) : une série de multiplications, on peut donc à priori classer cet algorithme dans l'ensemble E.

Cependant, on peut vérifier si notre solution est correcte en beaucoup moins de temps : en faisant la somme des distances des trajets parcourus, on obtient une distance qui doit nécéssairement être inférieure à D. L'algorithme de vérification appartient à la classe P, car le temps de calcul est proportionnel au nombre de villes.

Ces deux éléments (calcul dans E et vérification dans P) suffisent à classer notre problème dans la catégorie NP.

En plus de cela (la démonstration m'est inconnue) ce problème est un problème "NP difficile", un problème NP-Complet. On peut reformuler la conjecture P = NP comme cela :

Si on parvient à trouver un algorithme déterministe à temps polynomial pour résoudre le problème du voyageur, alors on pourra le faire pour n'importe quel problème NP. La classe NP sera alors réduite à la classe P.

Le problème, c'est que personne n'a encore trouvé d'algorithme déterministe à temps polynomial pour aucun problème NP-Complet, donc pour l'instant, force est de constater que P n'est pas égal à NP !

Mon point de vue : P n'est pas égal à NP

Comme je l'ai dit dans la première partie de cet article, je ne suis pas un spécialiste, pourtant, en lisant divers articles sur le problème P = NP, dont l'excellent livre "les énigmes mathématiques du 3ème millénaire", je me suis mis à rêver d'une légitimité pour donner ma conception de ce problème... Voici mon idée, peut-être naïve ou stupide, mais c'est une idée...

Les problèmes NP consistent à effectuer plusieurs calculs, qui sont à priori pas tous nécéssaires, pour les résoudre : Dans le problème du voyageur, "si on a de la chance", on peut tomber sur le plus court trajet du premier coup, pas besoin de tous les calculer.

On peut se représenter les problèmes NP comme des calculs "en parallèle" (comme dans un circuit électrique), nous n'avons pas besoin "d'alimenter tous les circuits" pour arriver au résultat. Les problème NP sont des "calculs en OU".

J'ai dit plus haut que les problèmes P ou E sont des "calculs en ET". D'où la nécéssité d'effectuer TOUS les calculs pour arriver au résultat.

Les mathématiciens, car il existe de nombreuses méthodes (appelées heuristiques) pour trouver les meilleurs chemins, ont conjecturé qu'un problème NP ("calcul en OU") n'est pas aussi complexe qu'un problème E ("calcul en ET"). ET que donc, on pouvait réduire les problèmes NP à des problèmes P ("calculs en ET") beaucoup plus simples que le problème E ("calcul en ET") équivalent.

Mon idée est que pour un algorithme donné, il existe un seul "calcul en ET" et que celui-ci est nécéssairement le problème E d'origine. Je dirais donc que NP n'est pas inclus dans P mais qu'au contraire, NP est inclus dans E.

Je pense que le meilleur moyen de résoudre un problème NP est donc d'utiliser ces heuristiques ou des algorithmes non déterministes comme par exemple les algorithmes génétiques.

Car il est vrai qu'un problème NP se distingue d'un problème E, par la possibilité de "sauter" des étapes du calcul, mais je suis convaincu qu'il n'existe pas de "formule magique" pour effectuer ce choix, on peut simplement éviter de faire de "mauvais choix" (heuristiques), ou expérimenter des échantillons prometteurs de choix (algo génétique).

J'ai bien conscience qu'il s'agit d'un avis tranché, sans aucun vrai argument scientifique ou mathématique. J'essayerai d'étayer cette idée plus tard avec, si je peux, des arguments plus rigoureux ou à défaut, par d'autres images peut-être plus convaincantes.

Une dernière précision sur P = NP : on peut se poser la question de savoir si cette conjecture est démontrable (ou réfutable). Autrement dit, il y a trois réponses possibles à la question P = NP ?

1- Vrai
2- Faux
3- Indémontrable

J'ai dis que je pensais que la réponse était Faux, mais je dois avouer que la troisième solution est tentante : Cela pourrait signifier soit une limite dans les outils mathématiques à notre portée (3A), soit que la question n'a pas de sens dans l'absolu (3B).

En résumé, je pencherais pour la solution 2 ou - dans une moindre mesure - la solution 3B.

Et vous, qu'en pensez-vous ? Quelle solution vous semble la plus plausible ?

PS : Si j'ai commis des erreurs dans cet article, je vous prie de m'en excuser, je n'aime pas trop me documenter pour écrire, mon but n'était pas de faire une "leçon" sur la théorie de la complexité. N'hésitez pas à apporter des corrections si nécéssaire.