Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 4 von 16
Zurück zur Trefferliste

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

Zitieren Sie bitte immer diese 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?

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Martin Grötschel
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Komplexität; Komplexitätstheorie
MSC-Klassifikation: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.)
Datum der Erstveröffentlichung:14.12.2005
Schriftenreihe (Bandnummer):ZIB-Report (05-58)
ZIB-Reportnummer:05-58
Verlagspublikation: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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.