Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03427.jsonl.gz/2788

Anzeige
Algorithmen mit einer polynomialen Laufzeit von
Algorithmen mit exponentieller Laufzeit, also
Für viele Probleme der Informatik hat man noch keine effiziente Algorithmen gefunden, also solche mit polynomialer Laufzeit oder besser.
Komplexitätsklasse P
Definition
Die Komplexitätsklasse
Komplexitätsklasse NP
Definition
Die Komplexitätsklasse
P-NP-Problem
Unbekannt ist, ob die beiden Klassen
Beispiele
Faktorisierung
Ein solches Beispiel ist die Faktorisierung einer Zahl in ihre Primfaktoren.
Diese Aufgabe scheint einfach, wird aber für sehr grosse Zahlen sehr aufwändig!
Es ist kein polynomiales Faktorisierungsverfahren bekannt – es kann aber auch nicht ausgeschlossen werden, dass es ein solches gibt! Dieses sogenannte P-NP-Problem ist eines der grossen ungelösten Probleme der theoretischen Informatik.
SAT – Erfüllbarkeitsproblem der Aussagenlogik
Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von englisch satisfiability) ist ein Entscheidungsproblem der theoretischen Informatik. Es beschäftigt sich mit der Frage, ob eine gegebene aussagenlogische Formel
Beispiel einer solchen aussagelogsichen Formel:
Notation wie wir es von Python kennen:
python
F = (A or C) and (not A or D or not E) and (B or not D or E)
Aufgabe
Finde eine Belegung der boolean Variablen
A -
E, womit
F
True ergibt.
SAT gehört zur Komplexitätsklasse NP. Jedes Problem aus NP kann in polynomieller Zeit auf SAT zurückgeführt werden (Polynomialzeitreduktion).
Eine deterministische Turingmaschine kann SAT in exponentieller Zeit entscheiden, zum Beispiel durch das Aufstellen einer Wahrheitstabelle. Es ist kein effizienter Algorithmus für SAT bekannt und es wird allgemein vermutet, dass ein solcher Polynomialzeitalgorithmus nicht existiert. Die Frage, ob SAT in polynomieller Zeit gelöst werden kann, ist äquivalent zum P-NP-Problem.