Problèmes non résolus en informatique

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

La mise en forme de cet article est à améliorer (décembre 2025).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

Comment faire ?

Les points d'amélioration suivants sont les cas les plus fréquents. Le détail des points à revoir est peut-être précisé sur la page de discussion.

Les titres sont pré-formatés par le logiciel. Ils ne sont ni en capitales, ni en gras.
Le texte ne doit pas être écrit en capitales (les noms de famille non plus), ni en gras, ni en italique, ni en « petit »…
Le gras n'est utilisé que pour surligner le titre de l'article dans l'introduction, une seule fois.
L'italique est rarement utilisé : mots en langue étrangère, titres d'œuvres, noms de bateaux, etc.
Les citations ne sont pas en italique mais en corps de texte normal. Elles sont entourées par des guillemets français : « et ».
Les listes à puces sont à éviter, des paragraphes rédigés étant largement préférés. Les tableaux sont à réserver à la présentation de données structurées (résultats, etc.).
Les appels de note de bas de page (petits chiffres en exposant, introduits par l'outil « Source ») sont à placer entre la fin de phrase et le point final^{[comme ça]}.
Les liens internes (vers d'autres articles de Wikipédia) sont à choisir avec parcimonie. Créez des liens vers des articles approfondissant le sujet. Les termes génériques sans rapport avec le sujet sont à éviter, ainsi que les répétitions de liens vers un même terme.
Les liens externes sont à placer uniquement dans une section « Liens externes », à la fin de l'article. Ces liens sont à choisir avec parcimonie suivant les règles définies. Si un lien sert de source à l'article, son insertion dans le texte est à faire par les notes de bas de page.
La présentation des références doit suivre les conventions bibliographiques. Il est recommandé d'utiliser les modèles {{Ouvrage}}, {{Chapitre}}, {{Article}}, {{Lien web}} et/ou {{Bibliographie}}. Le mode d'édition visuel peut mettre en forme automatiquement les références.
Insérer une infobox (cadre d'informations à droite) n'est pas obligatoire pour parachever la mise en page.

Pour une aide détaillée, merci de consulter Aide:Wikification.

Si vous pensez que ces points ont été résolus, vous pouvez retirer ce bandeau et améliorer la mise en forme d'un autre article.

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 vue 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$ ».

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 avec $n$ Les états ont un mot synchronisant, doivent-ils 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