Liste ungelöster Probleme der Informatik

Dieser Artikel ist eine Liste ungelöster Probleme in der Informatik. Probleme der Informatik werden als ungelöst angesehen, wenn ein Experte in dem Bereich sie als ungelöst ansieht oder wenn verschiedene Experten sich bei einer Lösung eines Problems uneinig sind.

Komplexitätstheorie[Bearbeiten | Quelltext bearbeiten]

P-NP-Problem. Dies ist eines von sieben Millennium-Problemen.
NC-P-Problem
NP-co-NP-Problem
P-BPP-Problem
P-PSPACE-Problem
Wie ist die Beziehung zwischen BQP und NP?
Unique games conjecture
Ist die Exponentialzeithypothese wahr?
Gibt es Einwegfunktionen? Gäbe es Einwegfunktionen, so folgt P $\neq$ NP im P-NP-Problem.

Algorithmen[Bearbeiten | Quelltext bearbeiten]

Welches ist der schnellste Algorithmus zur Multiplikation zweier n-stelliger Zahlen?
Welches ist der schnellste Algorithmus zur Matrizenmultiplikation?
Kann eine Primfaktorzerlegung in Polynomialzeit durchgeführt werden?
Kann der diskrete Logarithmus in Polynomialzeit berechnet werden?
Kann das Graphen-Isomorphismusproblem in Polynomialzeit gelöst werden?
Können Paritätsspiele in Polynomialzeit gelöst werden?
Erlaubt die lineare Programmierung einen streng polynomialen Zeit-Algorithmus? Dies ist Problem #9 in der Problemliste von Smale.
Was ist die untere Grenze der Komplexität eines Algorithmus zur schnellen Fourier-Transformation? Kann ein solcher schneller sein als Θ(N log N)?
Kann das 3SUM-Problem in weniger als quadratischer Zeitkomplexität gelöst werden?
Verhalten sich Splay-Bäume dynamisch optimal?
K-Server-Problem