WikiDer > Computational Complexity Theory

Computational Complexity Theory ist ein Zweig von Theoretische Informatik und Mathematik die darauf abzielt, Rechenprobleme in eine Reihe von Kategorien zu klassifizieren, die auf die inhärente Schwierigkeit dieser Probleme hinweisen. Ein Rechenproblem ist ein Problem, das von einem Computer gelöst werden kann. Ein Beispiel für ein rechnerisches Problem ist, ob eine Zahl Ahle ist. Dies lässt sich mit a Primzahltest. Ein Problem wird als von Natur aus schwierig angesehen, wenn es viel Zeit oder Speicher für alle erdenklichen Algorithmen benötigt. Die Computational Complexity Theory beschreibt somit die praktischen Grenzen von Computern.

Geschichte

Die Komplexitätstheorie entstand in den Jahren 20 und 30 des 20. Jahrhundert. Diese Jahrzehnte waren der Höhepunkt eines gewaltigen "Wachstumsschubs" in der Mathematik, die ungefähr angefangen hatte 1870. Die Mathematik hatte sich seitdem von einer Sammlung einzelner Rechentechniken in eine abstrakte Wissenschaft verwandelt, eine ganze Prinzipien, Axiome, Sprachstrukturen und philosophisch Einblicke. Fortlaufende Veröffentlichungen von Peano, Dedekind, Frege, Weißkopf und Russell hatte eine Theorie und ein Verständnis aufgebaut, die es so aussehen ließen, als würden die Möglichkeiten nie enden.

Zu Beginn des 20. Jahrhunderts fand die Mathematik jedoch ihre eigenen Grenzen, in Form der Arbeit von Gödel, der bewiesen hat, dass es in jeder Theorie hinreichender Komplexität immer Aussagen gibt, die nicht beweisbar sind. Dieser Befund hat den Mathematikern jedoch keinen Dämpfer versetzt. Stattdessen stürzten sich Mathematiker auf die Frage, wo die Wasserscheide lag: Was war beweisbar und was nicht? Was konnte berechnet werden und was nicht?

Der Anfang der Antwort auf diese Fragen begann um 1936 Formen. Fast von dem Moment an, als die Frage gestellt wurde, ob ein Problem lösbar ist oder nicht, war klar, dass Fragen nur antwortete könnte durch die erste Einrichtung sein was genau ist eine rechnung. Wie funktioniert eine Berechnung? Was genau machen wir, wenn wir eine Berechnung durchführen? Es ist natürlich sehr schön, "2 2 = 4" auswendig sagen zu können, aber was genau passiert in unserem Kopf, dass wir 2 und 2 reinstecken und 4 rauskommt?

Veröffentlicht 1936 19 Alan Turing sein Turing Maschine, einer der Ersten Berechnungsmodelle: ein Diagramm, das genau zeigt, wie eine Berechnung funktioniert. Ungefähr zur gleichen Zeit veröffentlicht Alonzo-Kirche ein ganz anderes Berechnungsmodell, das Lambda-Kalkül. Die Veröffentlichungen führten zu einem spektakulären "kleinen Wettbewerb" zwischen Church und Turing, um zu zeigen, welches Modell die meisten Probleme und Algorithmen ausdrücken konnte (das ist jetzt Ausdruckskraft eines Modells genannt).

Nach dem Ende der "Zwillingsschlacht" (in einem wundersamen Unentschieden entschieden) führte die Einführung der Computermodelle zu einem ganz neuen Zweig des mathematischen Sports: der Komplexitätstheorie. Insbesondere Turings Modell eignete sich sehr gut für die Forschung, die für diese Wissenschaft zentral ist, denn Turings Modell ist ein Algorithmus sehr mechanisch: in kleinstmöglichen Schritten, sehr präzise, ​​in Form von "erst machst du das und dann machst du das". Beide Berechnungsmodelle ermöglichten die Beantwortung der Frage, was berechenbar ist und was nicht. Turings Modell ermöglichte aber auch die Frage, wie lange eine bestimmte Berechnung dauern würde. Daraus ergab sich die zweite, zentrale Frage der Komplexitätstheorie: das Verhalten von Algorithmen. Das Turing-Modell wurde erstmals verwendet, um die Komplexität von Algorithmen in der Publikation zu messen measure Zur Rechenkomplexität von Algorithmen von Juris Hartmanis und Richard E. Stearns 1965.

Turings Berechnungsmodell gewann schon bald außerhalb der harten Mathematik immense Bedeutung. Im 1939 brach die Zweiter Weltkrieg aus und Großbritannien brauchte einen Weg zu schnell DeutscheCodes brechen. Turings Berechnungsmodell erwies sich bald als hervorragend praktikabel in a elektrisch Maschine – die erste Computer wurde geboren. Nach dem Krieg blieb die Faszination für die Möglichkeiten der Turing-Maschine bei vielen. Auf der ganzen Welt gestartet mathematische Fakultäten damit klar kommen. Schließlich so sehr, dass sich das Studium der Möglichkeiten der Maschine verselbstständigte und einen eigenen Namen bekam: Informatik.

Die Komplexitätstheorie beschäftigt sich auch heute noch mit der Klassifizierung von Algorithmen nach dem Komplexitätsgrad und mit der Frage, wo genau die Grenze zwischen Berechenbar und Unberechenbar und zwischen Leicht Berechenbar und Schwierig liegt.

Die Komplexitätstheorie hat inzwischen auch in anderen Wissenschaften Einzug gehalten. Die paradigmatische Sichtweise scheint auch sehr nützlich zu sein, zum Beispiel in der Soziologie.

Rechenprobleme

Problemfälle

Ein Rechenproblem kann als eine unendliche Ansammlung von Problemfällen mit einer Lösung für jeden Fall betrachtet werden. Die Eingabe in eine Berechnung wird als Problemfall angesehen und sollte nicht mit dem Problem selbst verwechselt werden. Im Fall von a Primzahltest der Problemfall ist eine Zahl und die Lösung lautet "ja", wenn die Zahl eine Primzahl ist, und "nein", wenn dies nicht der Fall ist.

Diese Problemfälle werden als Schnur in einem Alphabet. Oft wird das Alphabet als binäres Alphabet genommen: {0, 1} Wie bei echten Computern müssen auch mathematische Objekte, die kein binärer String sind, als solche kodiert werden. Als binäre Darstellung kann eine Zahl codiert werden. Ein Graph kann dargestellt werden durch die Bogenmatrix oder eine Kontiguitätsliste.

Entscheidungsprobleme

Entscheidungsprobleme sind von zentraler Bedeutung für die Computerkomplexitätstheorie. Es handelt sich um spezielle Rechenprobleme, deren Antwort "ja" oder "nein" oder äquivalent: 1 oder 0 ist. Ein Entscheidungsproblem kann als a formelle Sprache, wobei ein Wort zur Sprache gehört, wenn der Problemfall die Antwort "ja" hat. Das Ziel ist die Entscheidung mit a Algorithmus, ob ein gegebener Eingabestring zur formalen Sprache gehört. Wenn dieser Algorithmus mit "ja" antwortet, wird gesagt, dass er die Eingabezeichenfolge akzeptiert. Wenn nicht, wird die Eingabezeichenfolge abgelehnt.

Problemfallgröße

Um die Schwierigkeit eines Rechenproblems zu messen, könnte man sich die Zeit ansehen, die der beste Algorithmus benötigt, um das Problem zu lösen. Die Laufzeit kann jedoch vom Problemfall abhängen. Genauer gesagt haben größere Problemfälle eine längere Laufzeit. Daher wird die Laufzeit (oder ein anderes Maß für die Komplexität, z. B. der Raum) als Funktion der Größe des Problemfalls berechnet. Im Allgemeinen wird die Größe als die Anzahl der Bits definiert, die benötigt werden, um den Problemfall darzustellen.

Wenn die Größe der Eingabe nein ist, kann die Laufzeit als Funktion von . ausgedrückt werden nein. Bei gleich großen Problemfällen kann die Zeit unterschiedlich sein. Daher wird die Worst-Case-Komplexität zu T(nein) als maximale Laufzeit über alle Größeneingaben genommen taken nein. Wenn T(nein) ist polynomiell bezüglich nein, nennt man dies einen polynomialen Zeitalgorithmus.

Modelle und Komplexitätsmaße

Turing Maschine

sehen Turing Maschine für den Hauptartikel zu diesem Thema.

Eine Turingmaschine ist ein mathematisches Modell eines Computers. Es ist eine theoretische Maschine, die Papierstreifen verwendet und darauf Symbole schreibt und liest. Turing-Maschinen sollen keine echten Computer sein, sondern eher ein Gedankenexperiment, das einem Computer ähnelt. Das Church-Turing-Hypothese besagt, dass es eine Turingmaschine gibt, die das Problem löst, wenn es einen Algorithmus für ein Problem gibt. Es ist bekannt, dass die Turing-Maschine alle Probleme löst, die in anderen uns bekannten Modellen (wie RAM-Maschinen, Conways Spiel des Lebens, Zellulare Automaten und alle Programmiersprachen) auch lösen können. Da Turing-Maschinen sich gut für die mathematische Analyse eignen und als genauso leistungsfähig gelten wie andere Modelle, werden Turing-Maschinen am häufigsten in der Theorie der rechnerischen Komplexität verwendet.

Siehe auch

• Theorie komplexer dynamischer Systeme

Siehe die Kategorie Computational Complexity Theory von Wikimedia Commons für Mediendateien zu diesem Thema.