Blog post

Bestimmung und Aussagekraft von Komplexitätsklassen

Anna Lena Fehlhaber

Komplexität ist ein Charakteristikum neben Korrektheit und Terminierung von Algorithmen. Sie kann durch die Bestimmung von Komplexitätsklassen angegeben werden.

Diese Messung der Komplexität wird maßgeblich durch den Ressourcenaufwand, also die Laufzeit einer Polynomfunktion und ihrem Speicherverbrauch bestimmt. Bei der konkreten Umsetzung ist sie abhängig vom verwendeten Gerät, der Implementierung in der verwendeten Programmiersprache und weiteren Faktoren. Zur Bestimmung des Speicherplatzes werden Ram-Zellen, zur Bestimmung der Laufzeit die Ram-Befehle als Referenz genutzt. Durch die varianten Optionen werden die Komplexitätsklassen zumeist mit Hilfe sogenannter Schranken angegeben, die die untere, mittlere und obere Grenze des Ressourcenbedarfs bestimmen. Letztgenannter wird in eine Komplexitätsklasse überführt und bestimmt die Komplexität des Algorithmus.

Zwischen dem Bedarf an Speicherplatz und Laufzeit und der Größe der Eingabe besteht ein Abhängigkeitsverhältnis. Dieses beschreibt das Verhalten und Wachstum eines Algorithmus respektive dessen Komplexität in Abhängigkeit zur Eingabelänge. Hierfür kann die Landau-Notation verwendet werden.

Es wird in mathematische Entscheidungs- und Optimierungsprobleme unterschieden, für die die Komplexität bestimmt werden kann. In der theoretischen Informatik liegt ein besonderes Augenmerk auf den Klassen P, NP, NPC, NPI, co-P und co-NP. Die bekanntesten Klassen sind die beiden erstgenannten, kryptografische Algorithmen können jedoch insbesondere bei der Umsetzung als Suchalgorithmus außerhalb dieser liegen. Selbst wenn ein mathematisches Problem beispielsweise in der Klasse P liegt geht damit nicht einher, dass ein Algorithmus bekannt ist, der das Problem in Polynomialzeit zu lösen vermag.

Als solches sind die Komplexitätsklassen hilfreich, um sich die Dimension des mathematischen Problems, auf dem der Algorithmus aufbaut, zu vergegenwärtigen und auch Prognosen für die zukünftige Sicherheit anzustellen, ein kategorisches Ausschließen von Algorithmen aufgrund der zugeordneten Komplexitätsklasse ist hingegen nicht sinnvoll.

Verwendete Literatur:

  • Wagner (2011): Theoretische Grundlagen der Informatik.
  • Ziegenbalg et al. (2016): Algorithmen von Hammurapi bis Gödel. 4. überarb. Aufl..

 

Comments (1)

Leave a comment

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Prev Post Next Post