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

• 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

• 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

• POPLmark
• Barendregt–Geuvers–Klop-Vermutung
• Generalized star height problem

Weitere Probleme

• Aanderaa–Karp–Rosenberg-Vermutung

Siehe auch

• Liste ungelöster Probleme der Physik
• Ungelöste Probleme der Mathematik

Weblinks

• 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.
• The Open Problems Project – open problems in Computational Geometry and related fields.
• The RTA list of open problems – open problems in rewriting.
• The TLCA List of Open Problems – open problems in area typed lambda calculus.