Previous Contents Next

14   ``Harte'' Probleme

Literatur: Verschiedenes aus [CLR90] oder "ahnlichem. Vor allem Kapitel 36. Dazu Kapitel 11 aus [HU79]. Ein (schwieriges) Standardwerk zur Komplexit"atstheorie ist [Pap94].
Inhalt Komplexit"atsklassen P und NP Algorithmisch harte Probleme
Harte Probleme


Problem des Handlungsreisenden
Komplexit"atsklasse NP


Definition 12  [NP]   Die Komplexit"atsklasse NP ist die Klasse von Problemen, die nichtdeterministisch-polynomiell gel"ost werden kann.
Die Klasse NP


Reduzierbarkeit und Komplexit"atsklassen
Definition 13  [Polynomielle Reduktion]   Ein Problem L1 (Sprache) ist reduzierbar in polynomieller Zeit auf L2 (L1p L2, wenn es einen in polynomieller Zeit berechenbaren Algorithmus (Turingmaschine, ...) f gibt soda"s: x L1 gdw. f(x) L2.
NP-Vollst"andigkeit
Definition 14  [NP-vollst"andig]   Ein Problem L aus der Klasse NP ist NP-vollst"andig, falls sich alle Probleme aus der Klasse NP sich polynomiell auf L reduzieren lassen.

Beispiele
February 5, 2002
Previous Contents Next