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 » ou conjecture : « on a ».

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. 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 = Conjecture des jeux uniques L' 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 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.

La est-elle équivalente en temps polynomial au problème de l'isomorphisme de graphes ? Est-il possible de reconnaître les et les puissances -feuilles en temps polynomial ? Les jeux de parité peuvent-ils être résolus en temps polynomial ? Peut-on calculer la entre deux arbres binaires en temps polynomial ? Peut-on reconnaître en temps polynomial des graphes de largeur de clique bornée ? Peut-on trouver une sur un polyèdre convexe en temps polynomial ? Peut-on trouver en temps polynomial un avec des arêtes fixes pour deux graphes donnés ? . Le 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 ? Quel est l'algorithme le plus rapide pour multiplier deux nombres à chiffres ? Quelle est la complexité temporelle moyenne minimale possible de Shellsort avec une séquence d'intervalles fixes déterministes ? Le problème peut-il être résolu en temps fortement sous-quadratique, c'est-à-dire en temps pour un certain ? Est-il possible de calculer la distance d'édition entre deux chaînes de longueur en temps fortement sous-quadratique ? (ceci n'est possible que si l' fort est fausse) Le tri X + Y peut-il être effectué en un temps ? 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 pour un certain ? Le lemme de Schwartz-Zippel pour les 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 ? 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 à ?

Théorie des langages de programmation

: 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 à états a un mot synchronisant, doit-il en avoir un d'une longueur maximale ? : 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 ? : 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 ? Est-ce que tous les automates cellulaires élémentaires sont Turing-complet ? Déterminez si la longueur du mot minimal inachevable de est polynomial en , ou même dans . Il est connu que est un code à longueur variable si pour tous implique pour tous . 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 de sorte que la concaténation de et en base 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

Liens externes

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é.

Catégorie:Conjecture Catégorie:Problème non résolu