Polynomialzeit

Stichpunkte

Allgemein
	wenn die Rechenzeit m mit der Problemgröße n nicht stärker als mit einer Polynomfunktion wächst
	In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar
	Die besondere Bedeutung der Polynomialzeit besteht darin
	dass man sie als eine Grenze zwischen praktisch lösbaren und praktisch nicht lösbaren Problemen betrachtet
	die nicht in Polynomialzeit lösbar sind
	explodiert derart schnell
	Der Aufwand für Probleme
	dass sie schon für geringe Problemgrößen praktisch als unlösbar gelten müssen. Inhaltsverzeichnis showTocToggle("Anzeigen"
	"Verbergen") 1 Formale Definition 2 Superpolynomialzeit 3 Bezug zu den Komplexitätsklassen 4 Kritik [Bearbeiten]
Formale Definition
	In mathematischer Schreibweise gemäß der Landau-Notation: m(n) = O(nk)
	wobei k eine Konstante ist. [Bearbeiten]
Superpolynomialzeit
	c konstant). [Bearbeiten]
	heißen in Superpolynomialzeit lösbar
	Probleme
	ein Beispiel dafür ist exponentielle Zeit (m(n) = O(cn)
	deren Berechnungszeit mit der Problemgröße stärker als mit einer Polynomfunktion wächst
Bezug zu den Komplexitätsklassen
	die sich auf einer deterministischen sequentiellen Maschine in Polynomialzeit lösen lassen
	wird als P (von polynomial) bezeichnet
	Die Klasse aller Probleme
	Die Klasse aller Probleme
	wird als NP (von nondetermistic-polynomial time) bezeichnet
	die sich von einer (hypothetischen) nichtdeterministischen Maschine lösen lassen
	dass <math> P subseteq NP <math>
	Es ist klar
	also P eine Teilmenge von NP ist
	also <math> P neq NP <math>
	Eine bis heute unbewiesene Vermutung ist
	dass wirklich beide Klassen verschieden sind
	Diese Frage wird P/NP-Problem genannt und gilt als wichtigstes offenes Problem der Theoretischen Informatik. [Bearbeiten]
Kritik
	Die Polynomialzeit wurde bereits in den 1970er Jahren als Grenze zwischen den praktisch lösbaren und den praktisch unlösbaren Problemen angesehen
	ob diese Sichtweise aufgrund der drastischen Verschnellerung moderner Computerhardware angepasst werden muss
	Es stellt sich die Frage
	ob nicht auch Polynome hohen Grades eine Aufwandsexplosion zur Folge haben
	Umgekehrt kann die Frage gestellt werden
	die praktisch nicht mehr zu handhaben ist
	Die Polynomialzeit erscheint somit als recht willkürliche Grenze der Machbarkeit
	Es lassen sich jedoch eine Reihe von Gründen für die Beibehaltung dieser Sichtweise anführen
	dass Probleme
	die zunächst nur mit schlechtem polynomiellen Aufwand lösbar waren
	jeweils recht bald auch mit niedrigem polynomiellem Aufwand (etwa vom Grad 2 oder 3) gelöst werden konnten
	Insbesondere hat sich herausgestellt
	dass der algorithmische Aufwand meist auf Polynome niedrigen Grades zurückgeführt werden kann
	Offensichtlich bilden Polynomfunktionen eine so zusammenhängende Struktur
	dass dies zumindest aus der Sicht der theoretischen Informatik kaum als gerechtfertigt erscheint
	Andererseits würde eine Beschränkung der praktisch machbaren Probleme etwa auf die in Linearzeit lösbaren Probleme eine derart große Gruppe bedeutsamer Algorithmen ausschließen
	Dies bedeutet jedoch nicht
	dass auch eine Polynomialzeit niedrigen Grades in der Praxis bereits als inakzeptabel gelten kann. en:Polynomial time es:Tiempo polinómico ja:多項�時間

Dieser Artikel basiert auf dem Artikel Polynomialzeit 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.