Beschreibung
In diesem Buch werden theoretische, praktische und experimentelle Ansätze für den Beweis der Äquivalenz oder Nicht-Äquivalenz von Komplexitätsklassen vorgestellt, die als relationale Theorie bekannt sind.Sowohl Beweise als auch Widerlegungen werden auf der Grundlage des "P versus NP"-Theorems erbracht, das zuerst von Stephen Cook erfunden wurde und später eine tiefgreifende Anwendung für die Analyse der Leistung von Algorithmen fand, wodurch die Definition der Optimierungstheorie und die Theorie der Beschreibung dieser Leistung in Begriffen gegeben wurde, die gut geeignet sind und als kleine O- oder große O-Notation bekannt sind - der Medianwert existiert ebenfalls.
