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
- 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 NP im P-NP-Problem.
Algorithmen 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
Theorie der Programmiersprachen Bearbeiten
- POPLmark
- Barendregt–Geuvers–Klop-Vermutung
- Generalized star height problem
Weitere Probleme Bearbeiten
- Aanderaa–Karp–Rosenberg-Vermutung
Siehe auch Bearbeiten
Weblinks Bearbeiten
- Major unsolved problems in theoretical computer science on StackExchange.
- Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
- – open problems in Computational Geometry and related fields.
- – open problems in rewriting.
- The TLCA List of Open Problems – open problems in area typed lambda calculus.