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.