Au Joyeux Ragondin

Le problème de coloration de graphe (peut-on colorier les sommets d'un graphe avec k couleurs sans que deux sommets voisins aient la même couleur) est un des problèmes classiques d'algorithmique qui sont connus pour être NP-complets. La célèbre conjecture (P != NP) postule que pour certains problèmes, dont les problèmes NP-complets, il n'existe pas d'algorithme les résolvant en temps polynomial. La preuve de cette conjecture permettrait de répondre, enfin, à la question "existe-t-il des problèmes difficiles". Bien entendu, cette preuve a toujours défié mathématiciens et informaticiens.

Jusqu'à recemment en tout cas. Le mois dernier, le mathématicien Edwin Eutch, se basant sur des travaux d'Alfred Tarski, a proposé un algorithme polynomial permettant de décider la k-colorabilité. Dans ce genre de cas, il ne faut pas se précipiter: de nombreuses preuves ont été avancées, et rejetées. Mais après de nombreuses relectures, l'article a été accepté et publié, ce qui est déjà beaucoup. Inutile de préciser que la communauté est en émoi.

L'article est bien entendu très technique, et je vous invite à le lire pour vous faire une opinion, mais je vais quand même en esquisser l'idée générale. L'obstacle dans tous les problèmes NP-complets est l'explosion combinatoire qui fait que l'on ne peut pas (dans un temps raisonnable) explorer tous les cas possibles. Par exemple dans le cas de la k-coloration, il est possible de vérifier toutes les colorations possibles pour un graphe donné, mais leur nombre est trop élevé pour que cela soit une technique raisonnable. Tarski et Eutch se basent sur un résultat de théorie de l'information formulé par J.P. Pernod et F. Nyues qui prétend qu'il est possible de ne considérer qu'une partie très réduite de l'information sans diminuer la qualité du résultat. L'algorithme effectue une décomposition du graphe d'entrée en un nombre réduit de sous-graphes appelés motifs, et dont on connaît le nombre chromatique. Ces motifs (dont la figure ci-dessous donne des exemples) sont ensuite recomposés sans que la coloration soit rendue impropre, et ce en temps polynomial.

Après une visite la semaine dernière d'Henri Emmanuelli, venu pour promouvoir le "non" au référendum (mais qui avait oublié son argumentaire dans sa loge), Thierry Ardisson recevait ce soir Pierre Lellouche, député UMP, venu vanter les mérites du "oui".

Attention, ce monsieur croit en la démocratie: il fallait demander son avis au peuple. Et aussi, surtout, il se garde bien d'être alarmiste. Mais bon le problème, c'est que le peuple n'a pas connu la guerre, on n'a plus peur des allemands, alors on ne se préoccupe plus de l'unité de l'Europe. Et si on rejette cette constitution, c'en est fini de cette belle communauté: l'Europe sera faible, désunie, chaotique, face aux autres grandes puissances menaçantes que sont les "cowboys" étasuniens, les chinois armés jusqu'aux dents et les indiens qui ont mis la main sur tous nos services de hotline (je paraphrase un peu là, attention). Bref, si vous croyez en l'Europe, vous devez voter oui.

Je reconnais, dans une certaine mesure, la validité de l'argument: une constitution pour l'Europe c'est bien. Mais la grande question, celle qu'évitent soigneusement ces prophètes de l'apocalypse, est la suivante: pourquoi est-ce que le rejet de cette constitution signifie-t-elle la fin du projet européen ? Certes, le "non" englobe bon nombre de positions, allant des gens qui refusent l'Europe jusqu'à de fervents partisans d'une Europe communiste, en passant par toutes les nuances. Mais quoi, les hommes politiques vont-il tous démissionner si le vilain peuple il est méchant avec eux ? Est-ce que leur métier n'inclut pas la tâche de faire une constitution qui soit approuvée par le peuple ?

Pour prendre un exemple, considérons le fait que ce texte inclue d'une part une constitution, et d'autre part un traité définissant les grandes lignes d'une politique économique. La partie économique étant ouvertement et franchement libérale, elle va motiver le rejet de l'ensemble du texte par une partie de la population qui ne serait pourtant pas hostile à l'Europe ou à la constitution. Est-ce qu'on ne peut pas imaginer, par exemple, qu'en cas de refus du texte entier, des consultations soient effectuées sur des parties du texte ? Oui, cela prendra du temps, mais est-il raisonnable de jeter ainsi le bébé avec l'eau du bain, comme on nous menace de le faire ?

Avertissement: je vais céder à la vague de politisation qui déferle en ce moment sur l'Europe, et parler du traité pour la constitution. Comme je n'ai pas encore décidé ce que j'allais voter, il ne faut pas voir dans ce que je vais dire pendant les semaines à venir un argumentaire pour le "non" ou pour le "oui".

Lors du référendum du 29 mai, nous dit-on, il faudra faire attention à bien répondre à la question que l'on nous pose, et à ne pas profiter de l'occasion pour exprimer nos désaccords sur d'autres problèmes. Il ne faudra pas, par exemple, voter "non" pour protester contre la manière dont la directive sur les brevets logiciels a été traîtée, ou contre la politique de notre gouvernement. Jusque là, d'accord.

Mais quelle est la question posée ? C'est une chose importante à préciser avant de se décider. Je ne connais pas la formulation qu'utilisera le référendum, mais il demandera, en substance, si nous sommes d'accord pour adopter cette constitution. Il y a deux manières de comprendre cette question : soit (1) on nous demande si on considère cette constitution comme (assez) bonne pour l'Union Européenne, soit (2) on nous demande si elle est suffisamment meilleure que ce qu'on a actuellement pour être acceptée. Évidemment, si on la trouve bonne, on répond "oui" aux deux questions, mais si on ne la trouve pas bonne dans l'absolu, il est encore possible de répondre "oui" ou "non" à la deuxième question.

Dans l'idéal, la question posée est (1), ça ne devrait pas soulever la moindre objection. Pourtant, la plupart des partisans du "oui" essayent d'expliquer aux partisans du "non" qu'il faut répondre à la question (2), pas à la (1). Dans une certaine mesure, c'est logique. L'Europe ne part pas de rien, il y a déjà des traités, et si le traité sur la constitution n'est pas ratifié, les anciens traités resteront valides encore un moment. Les changements entre la situation actuelle et le traité sont donc au moins aussi importants que le contenu réel du traité.

Le problème, c'est qu'on nous a distribué le texte du traité, pas la liste des différences entre ce traité et les précédents. Et comme l'Europe est construite sur une pile de traités qui se modifient l'un l'autre, il n'est pas du tout évident de saisir l'ampleur de ces différences. Il serait déjà surprenant que la majorité des gens se motivent pour lire et comprendre le texte du traité, je ne crois pas une seconde qu'il vont trouver le temps et l'envie de le comparer avec les anciens traités. Et même si on entend souvent des affirmations expliquant que "la constitution donne plus de pouvoir au parlement" (ou le contraire), c'est la plupart du temps sans détails et sans citations concrêtes. Pour que l'on réponde à la bonne question, il aurait fallu nous donner le bon document.

Mes biens chers frères, mes bien chères soeurs, l'industrie de la culture va mal, elle ne gagne pas autant d'argent qu'elle voudrait. Espérons pour elle que la vente en ligne de musique bridée va l'aider à gagner plus. Dans un registre plus intéressant, BoingBoing parle de Smithsonian Global Sound, un site de vente en ligne de musique « du monde » qui semble vouloir faire les choses bien. Comme sur iTunes, un titre coûte un dollar (un peu plus s'il dure longtemps), mais la comparaison s'arrête là. Sur le plan du contenu, on peut écouter et encourager des artistes locaux souvent peu connus. Sur le plan de la technique, on obtient de la musique sans DRM, et dans un format libre sans perte de qualité, le FLAC. (vous pouvez aussi choisir le MP3 si vous y tenez, mais bon...)

What Des-Cartes did was a good step. You have added much several ways, & especially in taking ye colours of thin plates into philosophical consideration. If I have seen further it is by standing on ye shoulders of Giants.

Newton à Hooke

Le grand public aime avoir des héros, y compris parmis les scientifiques. Dans un réflexe d'auto-défense, les chercheurs ne se privent jamais de rappeler que les vrais esprits révolutionnaires sont rares, et que la découverte scientifique est un travail collectif. Bien que le travail de Darwin sur la sélection naturelle ait été fondateur, l'idée d'une évolution des espèces était dans l'air du temps. Si Darwin n'avait pas publié The Origin of Species, la découverte de la sélection aurait sans doute pu prendre plus longtemps, mais aurait été faite. En fait, d'autres avaient proposé des hypothèses similaires. Les révolutions scientifiques pourraient donc être le fait de personnes qui sont capables de saisir les bribes de théories que l'on trouve dans l'air, de choisir celles qui sont pertinentes, de les ordonner et d'en faire quelque chose. Alors, en attendant que le nouvel Einstein se révèle, est-il possible de jeter un coup d'oeil dans ce qui flotte actuellement, et d'avoir un aperçu de la prochaine révolution ?

Parmis les domaines en vogue en ce moment, on trouve la physique quantique, dont une interprétation conduit à conclure en l'existence d'un ensemble d'univers parallèles. Il est possible d'essayer d'interpréter le temps en termes d'univers parallèles, bien qu'aucune théorie ne se soit affirmée à ce sujet. On trouve aussi l'étude des phénomènes d'émergence. Le terme est vague, mais c'est définitivement un buzzword à la mode. Il s'agit d'adopter un point de vue holiste et d'étudier en quoi le tout est plus que la somme des parties. Par exemple, observer l'émergence de comportements de niveaux supérieurs dans une fourmilière, qui résultent de l'action d'individus n'ayant pas de plan global. Enfin, on trouve l'étude de l'intelligence, ou de la conscience, sur laquelle l'homme s'est toujours penché, mais qui a trouvé une nouvelle jeunesse depuis l'apparition des ordinateurs. Certains supposent que le temps puisse être un phénomène émergeant du multivers, c'est à dire que dans l'ensemble de tous les univers existant, certaines successions d'univers se distinguent des autres en ce que leur différence peut être décrite par les règles de la physique. On peut étendre cette hypothèse, et supposer que la conscience soit un phénomène émergeant du multivers, en suivant le même raisonnement.

Les philosophes se sont beaucoup intéressés à la nature de la réalité, et aux objets que nous manipulons en esprit. Par exemple, le nombre 2 a-t-il une existence réelle, ou bien s'agit-il d'une invention de notre esprit ? Pour Platon, les nombres (et les autres idées mathématiques) sont la réalité, mais nous n'en avons qu'une vision biaisée, tout comme l'ombre d'un objet décrit mal l'objet lui même. La question s'est faite plus pressante lorsque l'on a commencé à considérer sérieusement le fait que notre esprit puisse être un programme simulable par un ordinateur. Les programmes d'ordinateurs pouvant être représentés par des nombres, nous pouvons alors nous demander si un programme existe même sans qu'aucune machine ne l'exécute, et par extension, si toutes les consciences possibles existent sans qu'une machine (ou un cerveau) ne l'exécute.

Il est possible (bien que complètement infondé) de supposer que la vision platonicienne de la réalité puisse être remise au goût du jour. Et si seuls les nombres existaient ? Et si le phénomène d'émergence dont nous avons parlé plus haut faisait que certaines séquences de nombres, prises dans le bon ordre, décrivent une conscience ? Un univers ? Ce n'est, pour l'instant, que pure divagation, mais c'est un exemple de ce que l'on peut obtenir en prenant les problèmes à la mode et en les mélangeant ensemble. Le prochain changement de paradigme aura-t-il quelque chose à voir avec cela, ou bien sera-t-il complètement différent ?