Utilisateur:Ktz hulud/Liste de problèmes non résolus en informatique

This article is a list of unsolved problems in computer science. A problem in computer science is considered unsolved when an expert in the field (i.e, a computer scientist) considers it unsolved or when several experts in the field disagree about a solution to a problem.

Cet article est une liste de problèmes non résolus en informatique. Un problème en informatique est considéré comme non résolu quand un expert dans ce domaine (i.e, un informaticien) le considère comme ouvert ou quand plusieurs experts ne sont pas d'accord sur la solution à ce problème.

Computational complexity

• Problème P vs NP (souvent écrit « P = NP », ce qui n'est pas techniquement correct pour ce problème ou ceux en-dessous).
• Problème NC = P .
• Problème NP = co-NP .
• Problème P = BPP .
• Problème P = PSPACE .
• Problème L = NL .
• Problème L = P.
• Problème L = RL.
• Quelle est la relation entre BPP et NP ?
• Unique games conjecture
• ?
• Is the exponential time hypothesis true?
• Est-ce que les fonctions à sens unique existent ?
  • Est que la cryptographie à clef publique est possible ?

Algorithmes

• What is the fastest algorithm for multiplication of two n-digit numbers?
• Quelle est l'algorithme de multiplication de deux nombres de n chiffres le plus rapide ?
• What is the fastest algorithm for matrix multiplication?
• Quelle est l'algorithme de multiplication de matrices le plus rapide ?
• Can integer factorization be done in polynomial time on a classical computer?
• La décomposition en produit de facteurs premiers est-elle possible en un temps polynomial sur un ordinateur classique ?
• Can the discrete logarithm be computed in polynomial time on a classical computer?
• Can the graph isomorphism problem be solved in polynomial time?
• Le problème d'isomorphisme de graphe est il possible en un temps polynomial ?
• Can parity games be solved in polynomial time?
• Can the rotation distance between two binary trees be computed in polynomial time?
• Does linear programming admit a strongly polynomial-time algorithm? This is problem #9 in Smale's list of problems.
• What is the lower bound on the complexity of fast Fourier transform algorithms? Can they be faster than Θ (N log N)?
• Dynamic optimality conjecture for splay trees
• Can we compute the edit distance between two strings of length n in strongly sub-quadratic time, i.e., in time O(n^2−ϵ) for some ϵ>0 ?
• K-server problem
• Can X + Y sorting be done in strictly less than O(n² log n) time?
• Is there a bounded-time algorithm for envy-free cake-cutting?

Programming language theory

• POPLmark
• Barendregt–Geuvers–Klop conjecture

Autre problèmes

• Aanderaa–Karp–Rosenberg conjecture
• Generalized star height problem
• Separating words problem
• Possibility of hypercomputation
• Possibilité d'hypercalcul.

External links

• Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
• The RTA list of open problems – open problems in rewriting.
• The TLCA List of Open Problems – open problems in area typed lambda calculus.

{{unsolved problems}} {{DEFAULTSORT:List Of Unsolved Problems In Computer Science}} [[Category:Conjectures|*]] [[Category:Lists of unsolved problems|Computer Science]] [[Category:Unsolved problems in computer science| ]]