Back مبرهنة كوك وليفين Arabic Θεώρημα Κουκ-Λέβιν Greek Cook–Levin theorem English Teorema de Cook Spanish قضیه کوک–لوین Persian Théorème de Cook French משפט קוק-לוין HE Teorema Cook ID Teorema di Cook-Levin Italian 쿡-레빈 정리 Korean
Der kanadische Wissenschaftler Stephen A. Cook begründete 1971 eine neue Klasse von Problemen in der Komplexitätstheorie. Er zeigte, dass eine Teilmenge der Klasse NP existiert, auf die sich alle Probleme aus NP reduzieren lassen. Diese Teilmenge ist damit repräsentativ für die Schwierigkeit von NP und wird als NP-vollständig (NPC für englisch NP complete) bezeichnet. Der nach ihm benannte Satz von Cook sagt aus, dass das Erfüllbarkeitsproblem der Aussagenlogik (SAT, v. engl. satisfiability) NP-vollständig ist. Einen vergleichbaren Satz veröffentlichte Leonid Levin unabhängig von Cook im Jahre 1973, deswegen spricht man manchmal auch vom Satz von Cook und Levin.
Mit einem bekannten Vertreter der Klasse war der Nachweis für andere Probleme aus NP wesentlich einfacher zu führen, da es für ein Problem M aus NP nun ausreichte eine polynomielle Reduktion von SAT auf M zu konstruieren, um die NP-Vollständigkeit von M zu beweisen. Richard M. Karp erweiterte 1972 auf diese Weise NPC um 21 weitere Probleme, bis heute wurden mehrere hundert nachgewiesen.
© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search