P-NP-Problem SS09

Aus ProgrammingWiki

Archivierte Version vom 2009-05-25T12:42:33+00:00. Aktuelle Version

Inhaltsverzeichnis

TODO Marcel Schiwarth - Intro - Übersicht von Problemklassen

Definition:
P ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.

Definition:
Die Klasse der NP-Probleme ist die Menge aller Probleme, die nichtdeterministisch in Polynomzeit gelöst werden können.

Definition:
Seien A und B Sprachen (Probleme) mit A \subseteq \sum\nolimits_{1}^*