Modèles scientifiques

P=NP?

Question :

Est-ce que P=NP?

Réponse :

link

« Is P equal to NP?

In a 2002 poll of 100 researchers, 61 believed the answer is no, 9 believed the answer is yes, 22 were unsure, and 8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove.[5] »

Par contre si on examine cette question d’une perspective plus globale on peut reconnaître la nature de la difficulté (La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques).

link

« Le problème ouvert P=NP [modifier]

On a clairement P = NP car un algorithme déterministe est un algorithme non déterministe particulier, ce qui, dit en mots plus simples, signifie que si une solution peut être calculée en temps polynomial, alors elle peut être vérifiée en temps polynomial. En revanche, la réciproque : NP = P, qui est la véritable difficulté de l’égalité P = NP est un problème ouvert central d’informatique théorique. Il a été posé en 1970 indépendamment par Stephen Cook et Leonid Levin[5]. La plupart des spécialistes conjecturent que les problèmes NP-complets ne sont pas solubles en un temps polynomial. À partir de là, plusieurs approches ont été tentées. »

Si les ordinateurs du future offrent des possibilités de calcul ou représentation algébrique au delà de celles des technologies courantes, il se peut que nous puissions définitivement clore ce problème.

Selon les méthodes observées et portées à mon attention la réponse est non.

Je crois que la réponse future à cette question dépend à la fois des avancements théoriques et technologiques contribuant à ce domaine de problèmes, leurs démonstrations et leurs solutions.

Cela a une valeur importante qui doit être calibrée aux efforts requis dans d’autres domaines essentiels aux sociétés à venir.

- Paul Labbé

 


 

Le modèle de lois de la nature

Question :

Ma question concerne le modèle de lois de la nature utilisé en sciences. Etienne Wegner écrivait, dans un article des années 1960 accessible en ligne, que seules les choses relativement simples (et non faciles à comprendre) étaient assujetties aux lois de la nature, car ces lois ne peuvent être exprimées que pour des choses dont les conditions pertinentes sont détaillées, donc contrôlables. La complexité présente donc un défi pour un modèle de lois de la nature. (Je ne parle évidemment pas, ici, de modèle stochastique.) Une loi de la nature est un énoncé d’une tendance de la nature dans lequel on ne tient pas compte des circonstances d’un lieu physique, parce qu’il est possible de le faire. On peut cependant le faire parce qu’il n’y a aucune circonstance pertinente. Il existe donc bon nombre de phénomènes pour lesquels un modèle de lois de la nature ne peut s’appliquer. Il semble que les scientifiques (physiciens et biologistes non spécialistes des systèmes) ne réfléchissent pas beaucoup à ces profondes implications paradigmatiques de complexité. Ma question est la suivante : cette lacune s’explique-t-elle par le fait que les chercheurs sont enfermés dans un paradigme réductionniste, ou est-ce plutôt à cause des détours qu’ils doivent prendre pour les non scientifiques qui investissent des fonds dans les projets de R et D? De plus, à propos de « particules fondamentales », peut on vraiment expliquer la société humaine comme l’effet de minuscules particules de matière s’entrechoquant les unes les autres collectivement, ou est-ce que l’aspect collectif n’ajoute pas, justement, de nombreuses autres dimensions de causalité?

Réponse :

C’est une question complexe; c’est pourquoi il n’est évidemment pas facile d’y répondre. Mais voici mon opinion, en deux parties.

D’abord, je crois qu’il faut faire une distinction entre « loi de la nature » et « prévisibilité ». Prenons exemple sur le temps, qui est un système entièrement déterministe – c’est à dire que toutes les variables (la température, l’humidité, la densité, les condensats et les particules, les masses [sol/eau], etc.) transpirent et interagissent selon des « lois de la nature » (thermodynamique, physique classique, etc.) bien connues et comprises. Bien que le temps soit entièrement déterministe, nous ne pouvons pas le prévoir en nous fiant sur des facteurs dont on sait qu’ils entraînent une certaine sensibilité pour les conditions initiales (et peut-être même considérés comme des lois de la nature). Il s’agit du phénomène souvent appelé « effet papillon », qui suggère que le battement des ailes d’un papillon en Chine peut mener à la formation d’une tornade en Floride. Ainsi, une suite entièrement déterministe de causes et d’effets (comme le temps, les écosystèmes, le marché) basée sur des « lois de la nature » demeure complètement imprévisible; c’est pourquoi il semble s’agir d’un système qui ne respecte aucune loi. Il importe de comprendre que les progrès réalisés en matière de prévisions météorologiques ne reposent pas tant sur l’amélioration des méthodes de « prévision », mais bien sur de meilleures techniques d’observation de l’état actuel au moyen de l’imagerie satellitaire.

Cela signifie qu’essentiellement, nous ne savons pas à quel point un phénomène peut être petit et faire une différence ni à quel point un phénomène peut être gros et ne faire aucune différence.

D’un autre point de vue, on pense que l’observation elle même peut modifier ou influencer le phénomène étudié – l’exemple le plus connu de cette théorie est la façon dont nous observons la lumière, soit sous forme de particules ou d’ondes. C’est d’abord l’observateur qui organise la réalité, qui établit les limites et la structure d’un système. Lorsque nous acceptons et comprenons l’interdépendance de tout ce qui existe, l’utilité du réductionnisme devient limitée, sans toutefois être nulle.

Cependant, tout cela ne répond qu’à une partie de votre question. L’autre concerne le paradigme d’approches réductionnistes visant à comprendre la nature. Là encore, nous devons faire la distinction entre ce que la science définit comme des « lois de la nature » et les modèles et théories concernant la façon dont nous comprenons l’application et les conséquences de ces lois. Le réductionnisme, en simple, suggère que si l’on arrive à comprendre les parties d’un système, on comprendra éventuellement la totalité du système. Essentiellement, c’est une façon de percevoir la nature comme un type de machine.

Le chaos et la complexité (récemment désignés par certains scientifiques et philosophes comme « chaoplexité ») suggèrent cependant qu’un tout est plus grand que la somme de ses parties – que les relations entre les parties doivent être incluses dans notre compréhension. Ce phénomène, ce que vous appelez « collectivité », est appelé émergence.

Les phénomènes émergents restent dépendants des parties qui les constituent, mais ils sont également réels du point de vue ontologique, c’est à dire qu’ils ne peuvent être compris ou analysés à partir de leurs parties. Par exemple, je sais tout ce qu’il y a à savoir à propos de l’hydrogène et de l’oxygène, mais je ne peux pas déterminer, à partir de ces connaissances, ce qu’est l’eau (H2O). De plus, une molécule d’eau ou même 1 000 molécules d’eau (une goutte d’eau a un ordre de grandeur d’environ 1022 molécules) ne me permet d’aucune façon d’anticiper et de comprendre l’humidité, la viscosité, la turbulence ni même la tension superficielle. Pourtant, l’humidité dépend entièrement de la combinaison de l’hydrogène et de l’oxygène dans un grand nombre d’émergences (elle ne se trouve pas dans les parties) à une certaines échelle des parties qui interagissent entre elles. Donc, pour étudier l’humidité, il faut chercher à la bonne échelle. Autre exemple : on ne peut comprendre les règles de la grammaire en étudiant des synapses. En effet, même si chaque humain possède dans son cerveau des fonctions de traitement de la parole, les langues particulières sont déterminées par les interactions sociales. Ainsi, bien que chaque action liée à la parole dépende nécessairement des événements synaptiques qui se produisent dans le cerveau, on ne peut pas déterminer quelle langue est traitée en étudiant seulement ces événements synaptiques.

En guise de conclusion – la science continue de découvrir, d’explorer et d’exploiter des lois de la nature, mais cela ne se traduit pas nécessairement par une capacité directe de prévoir et de contrôler. Toutefois, les humains excellent à comprendre comment exploiter l’incontrôlable, à certaines fins.

Finalement, la complexité (chaoplexité) représente la voie de la vie – des niveaux de plus en plus nombreux d’émergence (des touts qui deviennent plus grands que la somme de leurs parties et qui, à leur tour, deviennent des parties d’un plus grand tout). Chaque nouvelle « émergence » représente de nouvelles capacités, de nouveaux domaines d’action, c’est pourquoi elle doit être étudiée comme un nouveau domaine possédant son propre niveau de « lois de la nature » (tout comme les lois de l’interaction chimique dans les événements synaptiques ne mènent pas aux règles de la grammaire dans une langue donnée ni aux lois régissant la configuration moléculaire, « H2O » mène aux lois qui régissent la turbulence).

Je suis conscient que j’ai répondu à votre question par des exemples issus de disciplines scientifiques traditionnelles, souvent appelées « sciences exactes ». Comme scientifique, je suis d’avis que les sciences sociales sont les sciences les plus « complexes » – elles renferment les domaines dans lesquels la complexité et l’émergence doivent former le paradigme de recherche fondamental, car le domaine humain est plus grand que la somme de ses parties psychologique, sociale, culturelle, économique, politique et environnementale.

Votre question et, je l’espère, ma réponse, soulignent une force fondamentale du projet scientifique, qui est la capacité d’entreprendre la transformation radicale de ses propres théories, cadres et paradigmes, tout en continuant d’offrir un certain ensemble consolidé de connaissances et de méthodes.

- John Verdon

Date de modification :