P-NP-Problem WS13-14
Inhaltsverzeichnis |
Einleitung
Die Klassen P und NP
NP-Vollständigkeit
Polynomiale Reduktion
NP-schwere Probleme
NP-vollständige Probleme
Nachweis der NP-Vollständigkeit eines Problems
Satz von Steven A. Cook
Das Ramsey-Problem
Vorteile praktischer Unlösbarkeit
Nun kann aber die Unlösbarkeit bestimmter Probleme auch zu unserem Vorteil genutzt werden. Sie findet Anwendung in der Kryptographie, die sich mit Methoden der Geheimhaltung von Daten beschäftigt. Dabei ist die Kryptologie eng mit der Kryptographie verbunden. Sie stellt die Wissenschaft von den (offenen) Geheimschriften dar und bildet mit Hilfe der Kryptoanalyse Vorschriften zur Entzifferung von Code. In der Praxis greift man auf Ver- und Entschlüsselungsverfahren zurück, die nicht oder nur sehr schwer lösbar sind. Zur Verschlüsselung wird ein Schlüssel benötigt, der die zu übertragenden Daten codiert. Dieser Schlüssel muss dem Empfänger zur Verfügung gestellt werden, damit die codierten Daten wieder entschlüsselt werden können. Hierbei kann es allerdings zu Schwierigkeiten kommen: erfolgt die Übertragung des Schlüssels unverschlüsselt, kann von außen unbefugt auf gesendete Daten zugegriffen werden, was dem Ziel der Verschlüsselung widerspricht. Zudem können die abgefangenen Informationen manipuliert werden, ohne dass der Empfänger von der potenziellen Gefahr weiß. Wird der Schlüssel allerdings verschlüsselt übertragen, kann keine Decodierung der Daten vorgenommen werden, da der Schlüssel für den Empfänger nicht lesbar ist. Um dieses Problem bei der Übertragung des Schlüssels zu umgehen, kann man einen öffentlichen Schlüssel verwenden, der zum Beispiel beim RSA-Verfahren zum Einsatz kommt.
Übungen
Literaturverzeichnis
- Wagenknecht, Christian: Algorithmen und Komplexität, Fachbuchverlag Leipzig, 2003
- Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford: Algorithmen, eine Einführung,Oldenbourg Verlag, 2007