Quels sont les problèmes non résolus de l’informatique ?


Il y a des milliers, voire des millions, de problèmes ouverts en informatique. En voici une dizaine qui me viennent à l'esprit.

  • Le nondéterminisme accélère-t-il réellement le calcul ? (Est-ce que P=NP ?)
  • Les problèmes solubles avec peu d'espace peuvent-ils être résolus rapidement ? (Est-ce que P = PSPACE ?)
  • Le hasard accélère-t-il réellement les calculs ? (Est-ce que RP=P ? BPP=P ?)
  • Dans quelle mesure l'exploitation du calcul quantique accélère-t-elle réellement le calcul ? (Nous savons qu'elle a un certain effet, à cause de l'algorithme de Grover, mais dans quelle mesure ? Est-ce que BQP=P ?)
  • La non-uniformité accélère-t-elle réellement le calcul ?
  • Peut-on résoudre 3SAT en [math]2^{o(n)} [/math]temps ? (L'hypothèse du temps exponentiel)
  • Can kSAT peut-il être résolu en [math]O(2^{0.9999 n})[/math] temps pour tous les k ? (The Strong Exponential Time Hypothesis)
  • Can 3SUM être résolu en [math]O(n^{1.99999})[/math] time?
  • Can Sorting X+Y être résolu en [math]O(n^2)[/math] time ? En [math]O(n^{1.99999})[/math] time?
  • Can all-pairs shortest paths be solved in [math]O(n^{2.99999}) [/math]time?
  • Is the Unique Games Conjecture true?
  • Are monotone graph properties evasive ?
  • Les flux maximaux dans les graphes planaires peuvent-ils être calculés en temps O(n) ?
  • Les flux maximaux dans les graphes toroïdaux (non orientés, de capacité unitaire) peuvent-ils être calculés en [math]O(n^{1,49999})[/math] temps ? en [math]O(n log n)[/math] temps ? O(n) time?
  • Existe-t-il un algorithme implémentable pour trianguler les polygones en O(n) time?
  • Existe-t-il un algorithme implémentable pour décider si un graphe peut être dessiné sur un tore sans croisement d'arêtes en O(n) time?
  • Quel est l'ensemble complet des mineurs interdits minimaux pour les graphes toroïdaux ? Pour les graphes de genre 2 ? Pour les graphes de largeur d'arbre 4?
  • Peut-on convertir une grammaire sans contexte arbitraire de longueur en forme normale de Chomsky en [math]O(n^{1.9999})[/math] temps ? [O(n^{3/2})[/math] time?
  • Les arbres de jeu sont-ils dynamiquement optimaux ? Tout arbre de recherche binaire auto-ajustable en ligne est-il dynamiquement optimal ? Tout arbre de recherche binaire auto-ajustable hors ligne est-il dynamiquement optimal ?
  • Peut-on calculer le genre d'un nœud en temps polynomial ?
  • Qu'est-ce que le cinquième nombre de Ramsey R(5,5) ? Le sixième nombre de Ramsey R(6,6) ? Le septième R(7,7)?
  • Est-ce qu'il existe une preuve vérifiable par machine du théorème de la structure des graphes de Robertson et Seymour ? Qu'en est-il du théorème de classification des groupes simples finis ?
  • Quelle est la plus petite machine de Turing dont le comportement est indépendant de ZFC ?
  • Est-ce qu'une généralisation naturelle de Getting Over It est NP-hard ? PSPACE-dure ? Indécidable ?
  • Combien de léchages faut-il pour atteindre le centre du Tootsie Roll d'un Tootsie Pop ?

Et ceci n'est que de l'informatique théorique.