Problèmes non résolus en informatique

Cet article présente une liste des problèmes non résolus en informatique. Un problème est considéré comme ouvert ou non résolu lorsqu'aucune solution n'est connue (ou lorsque les experts du domaine sont en désaccord sur les solutions proposées). De plus, le concept de problème est vu au sens large, et peut être raffiné en questions ou conjectures (comme question : « a-t-on $P=NP$ » ou conjecture : « on a $P\neq NP$ ».

Complexité computationnelle

Problème P ≟ NP – Le problème P ≟ NP est une question majeure non résolue en informatique qui consiste à déterminer si tout problème dont la solution peut être vérifiée en temps polynomial non déterministe (NP) peut également être résolu en temps polynomial déterministe (P). Cette question a des implications profondes dans des domaines tels que la cryptographie, la conception d'algorithmes et la théorie du calcul^[1].
Problème : a-t-on égalité entre BQP et NP ?
Problème : a-t-on égalité entre NC et P ?
Problème : a-t-on égalité entre NP et Co-NP
Problème : a-t-on égalité entre P et BPP
Problème : a-t-on égalité entre P et PSPACE
Problème : a-t-on égalité entre L et NL (complexité)
PH = problème PSPACE
Problème L = P
Problème L = RL (en)
Conjecture des jeux uniques
L'hypothèse du temps exponentiel (en) est-elle vraie ?
L'hypothèse du temps exponentiel fort (SETH) est-elle vraie ?
Existe-t-il des fonctions à sens unique ?
La cryptographie à clé publique est-elle possible ?
Conjecture du log-rank (en)
Conjecture de Hartmanis-Stearns

Temps polynomial versus temps polynomial non déterministe pour des problèmes algorithmiques spécifiques

La factorisation d'entiers peut-elle être effectuée en temps polynomial sur un ordinateur classique (non quantique) ?
Le logarithme discret peut-il être calculé en temps polynomial sur un ordinateur classique (non quantique) ?
Est-il possible de calculer le vecteur le plus court d'un réseau en temps polynomial sur un ordinateur classique ou quantique ?
Le problème de l'isomorphisme de graphes peut-il être résolu en temps polynomial sur un ordinateur classique ?

Note : Le problème d'isomorphisme de graphes consiste à déterminer si deux graphes finis sont isomorphes, c'est-à-dire s'il existe une bijection entre leurs sommets et leurs arêtes, l'adjacence étant préservée. Bien que ce problème soit connu pour appartenir à la classe NP, on ignore s'il est NP-complet ou s'il est résoluble en temps polynomial. Cette incertitude le place dans une classe de complexité unique, ce qui en fait un problème ouvert important en informatique^[2].

La canonisation de graphe (en) est-elle équivalente en temps polynomial au problème de l'isomorphisme de graphes ?
Est-il possible de reconnaître les puissances de feuilles (en) et les puissances $k$ -feuilles en temps polynomial ?
Les jeux de parité peuvent-ils être résolus en temps polynomial ?
Peut-on calculer la distance de rotation (en) entre deux arbres binaires en temps polynomial ?
Peut-on reconnaître en temps polynomial des graphes de largeur de clique bornée ?^[3]
Peut-on trouver une quasi-géodésique fermée simple (en) sur un polyèdre convexe en temps polynomial ?^[4]
Peut-on trouver en temps polynomial un plongement simultané (en) avec des arêtes fixes pour deux graphes donnés ?^[5]
Le problème de la somme de racines carrées (en) peut-il être résolu en temps polynomial dans le modèle de la machine de Turing ?

Théorie algorithmique des nombres

Problème de Skolem : est-il décidable si une suite de récurrence linéaire algébrique possède un zéro ?
Le dixième problème de Hilbert sur le corps des nombres rationnels

Autres problèmes algorithmiques

La conjecture d'optimalité dynamique : Les arbres splay ont-ils un ratio de compétitivité borné ?
Arbre de Trémaux : Est-il possible de construire un arbre de recherche en profondeur dans NC ?
La transformée de Fourier rapide peut-elle être calculée en temps $o(n\,\log n)$ ?
Quel est l'algorithme le plus rapide pour multiplier deux nombres à $n$ chiffres ?
Quelle est la complexité temporelle moyenne minimale possible de Shellsort avec une séquence d'intervalles fixes déterministes ?
Le problème 3SUM (en) peut-il être résolu en temps fortement sous-quadratique, c'est-à-dire en temps $O (n 2-ϵ)$ pour un certain $ϵ > 0$ ?
Est-il possible de calculer la distance d'édition entre deux chaînes de longueur $n$ en temps fortement sous-quadratique ? (ceci n'est possible que si l'hypothèse du temps exponentiel (en) fort est fausse)
Le tri X + Y peut-il être effectué en un temps $o (n 2 log n)$ ?
Quel est l'algorithme le plus rapide pour la multiplication matricielle ?
Les chemins les plus courts entre toutes les paires peuvent-ils être calculés en temps fortement sous-cubique, c'est-à-dire en temps $O (V 3-ϵ)$ pour un certain $ϵ > 0$ ?
Le lemme de Schwartz-Zippel pour les tests d'identité polynomiale (en) peut-il être dérandomisé ?
La programmation linéaire admet-elle un algorithme en temps fortement polynomial ? (Il s'agit du problème n° 9 de la liste de problèmes de Smale)
Combien de questions sont nécessaires pour une découpe de gâteau sans envie (en) ?
Quelle est la complexité algorithmique du problème de l'arbre couvrant minimal ? Autrement dit, quelle est la complexité de l'arbre de décision associé à ce problème ? L'algorithme optimal pour calculer les arbres couvrants minimaux est connu, mais comme il repose sur des arbres de décision, sa complexité est inconnue.
Conjecture de Gilbert-Pollak : Le rapport de Steiner du plan euclidien est-il égal à $2/{\sqrt {3}}$ ?

Théorie des langages de programmation

Conjecture de Barendregt–Geuvers–Klop (en) : Tout système de types purs faiblement normalisant est-il également fortement normalisant ?

Autres problèmes

La logique linéaire multiplicative-exponentielle est-elle décidable ?
La conjecture d'Aanderaa-Karp-Rosenberg est-elle vraie ?
Conjecture de Černý : Si un automate fini déterministe à $n$ états a un mot synchronisant, doit-il en avoir un d'une longueur maximale $(n-1)^{2}$ ?
Problème généralisé de la hauteur d'étoile (en) : tous les langages réguliers peuvent-ils être exprimés à l'aide d'expressions régulières généralisées avec une profondeur d'imbrication limitée des étoiles de Kleene ?
Problème de séparation des mots (en) : Combien d'états sont nécessaires dans un automate fini déterministe qui se comporte différemment selon la longueur de deux chaînes de caractères données de longueur $n$ ?
Est-ce que tous les automates cellulaires élémentaires sont Turing-complet ?
Déterminez si la longueur du mot minimal inachevable de $M$ est polynomial en $l(M)$ , ou même dans $sl(M)$ . Il est connu que $M$ est un code à longueur variable si pour tous ${\displaystyle u_{1},...,u_{n},v_{1},...,v_{m}\in M},{\displaystyle u_{1}...u_{n}=v_{1}...v_{m}}$ implique ${\displaystyle n=m}et{\displaystyle u_{i}=v_{i}}$ pour tous $0<i\leq n$ . Dans de tels cas, nous ignorons encore s'il existe une borne polynomiale. Cela constitue un affaiblissement possible de la conjecture de Restivo (déjà réfutée en général, bien que les bornes supérieures restent inconnues).
Déterminer tous les entiers positifs $n$ de sorte que la concaténation de $n$ et $n^{2}$ en base ${\ce {b}}$ en utilisant au maximum k un caractère distinct, pour fixer b et k

De nombreux autres problèmes de théorie du codage figurent également parmi les problèmes non résolus en mathématiques.

Références

↑ (en) « P vs. NP – The Greatest Unsolved Problem in Computer Science », Quanta Magazine, sur Quanta Magazine, 1^er décembre 2023 (consulté le 11 mars 2025).
↑ (en) Erica Klarreich, « Landmark Algorithm Breaks 30-Year Impasse », Quanta Magazine, sur Quanta Magazine, 14 décembre 2015 (consulté le 11 mars 2025).
↑ (en) Michael R. Fellows, Frances A. Rosamond, Udi Rotics et Stefan Szeider, « Clique-width is NP-complete », SIAM Journal on Discrete Mathematics, vol. 23, n^o 2,‎ 2009, p. 909–939 (DOI 10.1137/070687256, MR 2519936, S2CID 18055798, lire en ligne [archive du 27 février 2019])
↑ (en) Erik D. Demaine et Joseph O'Rourke, Geometric folding algorithms: Linkages, origami, polyhedra, Cambridge, England, Cambridge University Press, 2007 (ISBN 978-0-521-71522-5, DOI 10.1017/CBO9780511735172, MR 2354878), chap. 24 (« Geodesics: Lyusternik–Schnirelmann »), p. 372–375
↑ (en) Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer et Schulz, Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22–24, 2006, Revised Papers, vol. 4271, Berlin, Germany, Springer, coll. « Lecture Notes in Computer Science », 2006 (ISBN 978-3-540-48381-6, DOI 10.1007/11917496_29, MR 2290741, lire en ligne), « Simultaneous graph embeddings with fixed edges », p. 325–335.

Liens externes

(en) Gerhard Woeginger, Open problems around exact algorithms. Discrete Applied Mathematics. 156 (2008): 397-405.
La liste des problèmes ouverts de la RTA - Problèmes ouverts en réécriture.
Liste des problèmes ouverts de la TLCA - Problèmes ouverts dans le domaine du lambda-calcul typé.

Portail de l'informatique théorique

[1] (en) « P vs. NP – The Greatest Unsolved Problem in Computer Science », Quanta Magazine, sur Quanta Magazine, 1^er décembre 2023 (consulté le 11 mars 2025).

[2] (en) Erica Klarreich, « Landmark Algorithm Breaks 30-Year Impasse », Quanta Magazine, sur Quanta Magazine, 14 décembre 2015 (consulté le 11 mars 2025).

[3] (en) Michael R. Fellows, Frances A. Rosamond, Udi Rotics et Stefan Szeider, « Clique-width is NP-complete », SIAM Journal on Discrete Mathematics, vol. 23, n^o 2,‎ 2009, p. 909–939 (DOI 10.1137/070687256, MR 2519936, S2CID 18055798, lire en ligne [archive du 27 février 2019])

[4] (en) Erik D. Demaine et Joseph O'Rourke, Geometric folding algorithms: Linkages, origami, polyhedra, Cambridge, England, Cambridge University Press, 2007 (ISBN 978-0-521-71522-5, DOI 10.1017/CBO9780511735172, MR 2354878), chap. 24 (« Geodesics: Lyusternik–Schnirelmann »), p. 372–375

[5] (en) Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer et Schulz, Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22–24, 2006, Revised Papers, vol. 4271, Berlin, Germany, Springer, coll. « Lecture Notes in Computer Science », 2006 (ISBN 978-3-540-48381-6, DOI 10.1007/11917496_29, MR 2290741, lire en ligne), « Simultaneous graph embeddings with fixed edges », p. 325–335.

[1]

[2]

[3]

[4]

[5]