@misc{Groetschel, author = {Gr{\"o}tschel, Martin}, title = {Das Problem mit der Komplexit{\"a}t: P = NP?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8916}, number = {05-58}, abstract = {Was Komplexit{\"a}t ist, weiß niemand so richtig. In vielen Wissenschaftsgebieten wird der Begriff Komplexit{\"a}t verwendet, {\"u}berall mit etwas anderer Bedeutung. Mathematik und Informatik hab en eine eigene Theorie hierzu entwickelt: die Komplexit{\"a}tstheorie. Sie stellt zwar grundlegende Begriffe bereit, aber leider sind die meisten wichtigen Fragestellungen noch ungel{\"o}st. Diese kurze Einf{\"u}hrung konzentriert sich auf einen speziellen, aber bedeutenden Aspekt der Theorie: L{\"o}sbarkeit von Problemen in deterministischer und nichtdeterministischer polynomialer Zeit. Hinter der f{\"u}r Uneingeweihte etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexit{\"a}tstheorie. Anhand dieser Fragestellung werden einige Aspekte der Theorie erl{\"a}utert und formell erkl{\"a}rt, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grunds{\"a}tzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es f{\"u}r viele Probleme unseres Alltags keine effizienten L{\"o}sungsmethoden gibt?}, language = {de} }