NP-Schwere

Stichpunkte

Allgemein
	NP-schwer bzw
	NP-hart (von englisch NP-hard
	abgekürzt für Non-deterministic Polynomial-time hard) ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik
	Er dient der Klassifizierung von Problemen
	die im Sinne der formalen Theorie besonders aufwändig zu berechnen sind
	also alle <math>L<math> aus NP polynomial reduzierbar auf <math>L_1<math> sind
	Sei <math>L_1 sub Sigma^*<math>
	also eine formale Sprache. <math>L_1<math> heißt nun NP-schwer
	falls <math>forall L in NP : L le_P L_1<math>
	wie jedes andere Problem aus NP
	Dies bedeutet
	dass <math>L_1<math> mindestens so schwer ist
	Es schließt jedoch nicht aus
	dass <math>L_1<math> selbst schwerer ist
	Insbesondere kann gelten: <math>L_1notin NP<math>
	ist das Halteproblem für Turingmaschinen. [Bearbeiten]
	also schwerer als alle NP-vollständigen Probleme
	das NP-schwer ist und nicht NP-vollständig
	Ein klassisches Beispiel für ein Problem
Siehe auch
	NP-Vollständigkeit en:NP-hard es:NP-hard ja:NP困難

Dieser Artikel basiert auf dem Artikel NP-Schwere aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.