P=NP?

Please always quote using this URN: urn:nbn:de:0297-zib-6939

Hinter der für den Uneingeweihten etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Dieser Artikel erläutert einige Aspekte der Theorie und erklärt informell, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt?

Metadaten
Author:	Martin Grötschel
Document Type:	ZIB-Report
Tag:	P=NP; computational complexity
MSC-Classification:	03-XX MATHEMATICAL LOGIC AND FOUNDATIONS / 03Dxx Computability and recursion theory / 03D15 Complexity of computation (including implicit computational complexity) [See also 68Q15, 68Q17]
	68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68-01 Instructional exposition (textbooks, tutorial papers, etc.)
	68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) [See also 03D15, 68Q17, 68Q19]
	68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
Date of first Publication:	2002/07/01
Series (Serial Number):	ZIB-Report (02-26)
ZIB-Reportnumber:	02-26
Published in:	Erschienen in: Elemente der Mathematik, Vol. 57, Nr. 3 (2002) 96-102

Open Access