J’ai demandé  à Nathan s’il pouvait être interessé par la résolution d’un problème mathématique. Il s’agissait d’Eternity II, un puzzle reconnu pour être l’un des plus difficiles au monde que seul l’emploi de mathématiques puisse résoudre. Il n’en avait jamais entendu parlé mais semblait interessé par le défit.

- Non pas que je puisse imaginer pouvoir le résoudre car s’attaquer à ce genre de problème en pensant trouver une solution relève du même orgueil que celui de vouloir se substituer à Dieu, mais je pense ainsi pouvoir à la fois parfaire mon apprentissage et laisser libre cours à mon imagination. Je vais faire des maths surréalistes !

Le lendemain, il m’expliqua qu’Eternity II était un problème avec compatibilité entre côtés entrant dans une catégorie dont il avait été prouvé en 2007 qu’elle était NP-Complète par Erik D. Demaine et Martin L. Demaine :

Depuis 1971 et d’après Cook, « Any NP problem can be converted to SAT in polynomial time. »

Nathan de se demander : 

- Est-il possible de dissocier le problème en sous-ensembles tels qu’entre deux états,  il existe au moins un « Equilibre de Nash » ?

- Ces équilibres peuvent-ils être atteind par une combinaison de pavages ?

-  Comment Christopher Monckton a-t-il établi ~20.000 solutions pour un peu moins de combinaisons ?

De fait, instinctivement, il lui semblait interessant, entre deux états que plusieurs machines de Turing non-déterministes puissent s’accorder sur une stratègie commune afin d’atteindre un maximin partiel. De plus, le fait d’avoir pour seule certitude que deux arêtes doivent être similaires pour former un ensemble de deux éléments compatibles lui rappelait la construction de pavages à la manière du tapis de Sierpiński.  Une dicipline qui l’avait particulièrement marquée une dizaine d’années auparavant. Encore fallait-il que Nathan puisse modèliser E2 avant de valider ou non certaines de ses hypothèses.

(A suivre)