Ungelöste Probleme der Informatik und Mathematik

Hallo zusammen

Es gibt doch Proleme, welche durch programmieren gelöst werden sollen.
Schafft man eines gibt es ein hohes "Preisgeld". Weiss jemand welche das
sind, respektive wo die im Internet beschrieben sind?

Ich meinte eines sei so eine art Routenplaner. Wo ein alogrithmus gesucht
wird, welcher die schnellste strecke ausrechnen kann ohne irgendwelche Wege
zweimal zu fahren.

Hallo,

Das mit dem Handlungsreisenden ist das Travelling Salesman Problem.
Zu den Problemen:
meinst du vielleicht Ungelöste Probleme der Mathematik?

Super, dass habe ich gesucht🙂 Danke!

Alle Probleme, die NP-Complete sind ... für diese ist nicht bekannt, ob's einen Algorithmus mit polynomialer Laufzeit gibt, der das Problem löst.

Allgemein: P = NP-Problematik

Ein super Buch zu dem Thema: "Computers and Intractability" von Garey et al.

Hallo Golo,

Alle Probleme, die NP-Complete sind ... für diese ist nicht bekannt, ob's einen Algorithmus mit polynomialer Laufzeit gibt, der das Problem löst.

die Komplexitätsklasse NP ist die Menge aller von nichtdeterministischen Turingmaschinen in Polynomialzeit lösbaren Probleme. Und da NP-vollständig eine Teilmenge von NP ist, heißt das, es gibt für diese Probleme auch jetzt schon einen Algorithmus mit polynomialer Laufzeit ... nur ist es eben ein Algorithmus für einen "Computer", wie es ihn (praktisch) noch nicht gibt. Wenn aber die Quantencomputer erst (praktische) Realität werden, könnten NP-vollständige Probleme auch (praktisch) in Polynomialzeit gelöst werden, selbst wenn P != NP. 🙂

herbivore