Un problème de la connaissance mathématique

Dans un système formel F, on se demande si on peut trouver une preuve de l'énoncé math S t.q. le nb de symboles de la preuve < n. Le problème est décidable, il faut chercher la preuve dans tout le code de F dont les cordes (bit-strings) < n (c'est comme si on faisait CTRL + F) et voir si parmi les 2^n possibilités on trouve une preuve F-valide, ce qui, si n = 1000, va nous faire 2^1000 exemples à traiter et on sera morts avant. La théorie de la complexité computationnelle travaille justement sur l'adéquation d'un problème et de sa solvabilité.

On distingue les P-problèmes des NP-problèmes. Les P-problèmes sont solvables en temps polynomial, les NP-problèmes ont une solution qui peut être trouvée en temps polynomial. Si P =! NP, alors il y a une intersection non-vide entre les NP-problèmes et les problèmes solvables en temps non-polynomial. A l'évidence, P ⊆ NP mais si P = NP, tout problème que l'on peut résoudre en temps polynomial a une solution en temps polynomial ("the ability to check the solutions to puzzles efficiently would imply the ability to find solutions efficiently").

En 2011, le GIMPS a identifié le plus grand nombre entier premier connu, aka p := 2^43112609 - 1. Que veut dire "connu"? (1) nous savons que p désigne un nombre entier et (2) nous avons prouvé que cet entier était premier. Mais sur cette base, nous pourrions déduire que (3) p' := le premier nombre premier t.q. p' > p. Mais que nous connaissions (1) et (2) & que (1) & (2) => (3), il ne suit pas que nous connaissions (3). Que j'ai la connaissance que je suis actuellement sur Terre (càd que si je n'y étais pas, je ne croirais pas que j'y suis et si j'y suis, je crois que j'y suis) n'implique pas que j'ai la connaissance que je ne suis pas un cerveau dans une cuve, pour reprendre un argument exposé par Nozick dans Philosophical Explanations. Si la connaissance était closed under known logical implication, il me suffirait de connaître les axiomes de Peano pour connaître tous les théorèmes possibles que l'on peut en déduire, même ceux qu'on n'a pas encore découverts, et de même pour toutes les axiomatiques, pour tous les jeux (à partir du moment où on en connaît les règles). Un autre point intéressant est que le test de connaissance en maths peut être positif ou négatif selon la façon dont la question est posée. Un enfant sait sans doute que 2+1 = 1+2 sans pour autant comprendre (let alone pouvoir démontrer) la commutativité de l'addition. Mais plus spécifiquement ici, la différence entre la connaissance de p et la connaissance de p' est que nous avons un algorithme qui produit p à partir d'un entier k t.q. p = 2^k - 1 en temps polynomial, alors que nous n'avons pas cet algorithme pour p'.

Lire Scott Aaronson, Why philosophers should care about computational complexity