• search hit 4 of 18
Back to Result List

Das Problem mit der Komplexität: P = NP?

Please always quote using this URN: urn:nbn:de:0297-zib-8916
  • Was Komplexität ist, weiß niemand so richtig. In vielen Wissenschaftsgebieten wird der Begriff Komplexität verwendet, überall mit etwas anderer Bedeutung. Mathematik und Informatik hab en eine eigene Theorie hierzu entwickelt: die Komplexitätstheorie. Sie stellt zwar grundlegende Begriffe bereit, aber leider sind die meisten wichtigen Fragestellungen noch ungelöst. Diese kurze Einführung konzentriert sich auf einen speziellen, aber bedeutenden Aspekt der Theorie: Lösbarkeit von Problemen in deterministischer und nichtdeterministischer polynomialer Zeit. Hinter der für Uneingeweihte etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Anhand dieser Fragestellung werden einige Aspekte der Theorie erläutert und formell erklärt, 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?

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Martin Grötschel
Document Type:ZIB-Report
Tag:Komplexität; Komplexitätstheorie
MSC-Classification: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 / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
97-XX MATHEMATICS EDUCATION / 97-01 Instructional exposition (textbooks, tutorial papers, etc.)
Date of first Publication:2005/12/14
Series (Serial Number):ZIB-Report (05-58)
Published in:Ersch. in: Kombinatorische Optimierung erleben - In Studium und Unterricht von Stefan Hußmann und Brigitte Lutz-Westphal. Aus der Reihe: Mathematik erleben. Unter Mitarbeit von Brieden, Andreas / Gritzmann, Peter / Grötschel, Martin / Leuders, Timo. Vieweg, 2007. ISBN: 978-3-528-03216-6 S.265-274