Eine Einführung in die Berechenbarkeitstheorie und Komplexität

Haben Sie sich jemals gefragt: Was genau ist das Gerät, auf dem Sie diesen Artikel lesen? Was ist ein Computer?

Computational Science geht auf eine Zeit zurück, lange bevor diese modernen Computergeräte überhaupt erdacht wurden. In einer Branche, in der sich die häufiger gestellten Fragen um Programmiersprachen, Frameworks und Bibliotheken drehen, haben wir die grundlegenden Konzepte, die einen Computer zum Ticken bringen, oft als selbstverständlich angesehen.

Aber diese Computer, die unendliches Potenzial zu besitzen scheinen – haben sie irgendwelche Grenzen? Gibt es Probleme, die Computer nicht lösen können?

In diesem Artikel werden wir uns mit diesen Fragen befassen, indem wir uns von den Besonderheiten von Programmiersprachen und Computerarchitekturen entfernen. Indem wir die Leistungsfähigkeit und Grenzen von Computern und Algorithmen verstehen, können wir unsere Denkweise verbessern und verschiedene Strategien besser begründen.

Die abstrakte Betrachtungsweise des Rechnens bringt Ergebnisse hervor, die sich über die Zeit bewährt haben und für uns heute genauso wertvoll sind wie zu der Zeit, als sie in den 1970er Jahren entwickelt wurden.

Berechenbarkeit

Was ist ein Computer? Was ist ein Problem?

In der Schule wird uns oft ein mentales Modell von Problemen und Funktionen beigebracht, das ungefähr so ​​lautet:

Eine Funktion ist eine Prozedur, die Sie auf eine Eingabe x anwenden, um eine Ausgabe f(x) zu finden.

Es stellt sich heraus, dass die mathematische Definition anders ist:

Eine Funktion ist eine Menge geordneter Paare, so dass das erste Element jedes Paars aus einer Menge X (genannt Domäne) stammt, das zweite Element jedes Paars aus einer Menge Y (genannt Kodomäne oder Bereich) und jedes Element aus die Domäne ist mit genau einem Element des Bereichs gepaart.

Das war ein ziemlicher Schluck. Aber was genau bedeutet das?

Diese Definition sagt uns, dass ein Computer eine Maschine für Rechenfunktionen ist.

Warum?

Weil Computer beliebige Eingaben in eine Ausgabe umwandeln. Mit anderen Worten, sie lösen Probleme. Die beiden Definitionen von Funktionen, die uns so vertraute und die formale, stimmen für viele praktische Zwecke überein.

Die mathematische Definition erlaubt uns jedoch, interessante Schlussfolgerungen zu ziehen, wie z. B. die Existenz nicht berechenbarer Funktionen (d. h. unlösbarer Probleme):

Denn nicht jede Funktion kann als Algorithmus beschrieben werden.

Spielregeln

Um unsere Argumentation zu erleichtern, stellen wir uns Computer als Maschinen vor, die Eingaben entgegennehmen, eine Reihe von Operationen ausführen und nach einiger Zeit Ausgaben liefern.

Wir nennen die Eingabe das Alphabet der Maschine; das heißt, eine Menge von Zeichenfolgen aus einer endlichen Menge. Beispielsweise kann das Alphabet der Maschine binär (0 und 1) oder der ASCII-Zeichensatz sein. Jede endliche Folge von Zeichen ist eine Zeichenfolge, z. B. „0110“.

Darüber hinaus werden wir die Ausgabe einer Maschine als binäre Annahme-Ablehnungs-Entscheidung darstellen, die geliefert wird, sobald die Maschine (hoffentlich) ihre Berechnung beendet hat. Diese Abstraktion passt gut zu der mathematischen Definition von Funktionen von früher.

Angesichts dieser Parameter ist es wichtig, einen weiteren Typ zu charakterisieren: eine Sammlung von Zeichenfolgen. Vielleicht interessieren wir uns für den Satz von Zeichenfolgen, den eine Maschine akzeptiert, oder vielleicht bauen wir eine Maschine, die Zeichenfolgen in einem bestimmten Satz akzeptiert und keine anderen, oder vielleicht fragen wir uns, ob es überhaupt möglich ist, eine Maschine zu entwerfen, die alles in einigen akzeptiert bestimmten Satz und keine anderen.

In all diesen Fällen wird eine Menge von Strings als Sprache bezeichnet – zum Beispiel die Menge aller binären Strings, die gerade Zahlen darstellen, oder die Menge von Strings, die eine gerade Anzahl von Zeichen haben. Es stellt sich heraus, dass Sprachen wie Zahlen mit Operatoren wie Verkettung, Vereinigung, Schnittmenge und dergleichen bearbeitet werden können.

Ein wichtiger Operator ist der Kleene-Sternoperator, der auch bei regulären Ausdrücken verwendet wird. Dies kann man sich als Vereinigung aller möglichen Kräfte der Sprache vorstellen. Wenn beispielsweise unsere Sprache A die Menge der Zeichenfolgen { '01', '1' } ist, dann ist ein Mitglied von A* die Zeichenfolge '0101111'.

Zählbarkeit

Das letzte Puzzlestück, bevor wir unsere Behauptung beweisen, dass nicht alle Funktionen berechenbar sind, ist das Konzept der Abzählbarkeit. Intuitiv wird unser Beweis zeigen, dass es mehr Sprachen gibt; Das heißt, mehr Probleme, als es mögliche Programme gibt, um sie zu lösen. Das funktioniert, weil die Frage, ob ein String in eine Sprache gehört (Ja/Nein), selbst ein Problem darstellt.

Genauer gesagt behauptet unser Beweis, dass die Menge möglicher Programme abzählbar unendlich ist, während die Menge der Sprachen über einem Alphabet überabzählbar unendlich ist.

An diesem Punkt denken Sie vielleicht: „Unendlichkeit ist an sich schon eine seltsame Idee; jetzt muss ich mich mit zweien auseinandersetzen!“

Nun, es ist nicht so schlimm. Eine abzählbar unendliche Menge ist eine Menge, die aufgezählt werden kann. Man kann sagen, dies ist das erste Element, dies ist das zweite Element und so weiter, wobei man schließlich jedem Element der Menge eine Zahl zuweist. Nehmen Sie zum Beispiel die Menge der geraden Zahlen. Wir können sagen, dass 2 der erste ist, 4 der zweite, 6 der dritte und so weiter. Solche Mengen sind abzählbar unendlich oder abzählbar.

Bei manchen Mengen, wie den reellen Zahlen, spielt es jedoch keine Rolle, wie schlau Sie sind; es gibt einfach keine Aufzählung. Diese Mengen sind überabzählbar unendlich oder überabzählbar.

Abzählbar viele Programme

Zunächst wollen wir zeigen, dass die Menge der Computerprogramme abzählbar ist. Für unsere Zwecke tun wir dies, indem wir beobachten, dass die Menge aller Zeichenketten über einem endlichen Alphabet abzählbar ist. Das funktioniert, weil Computerprogramme selbst endliche Zeichenketten sind.

Der Beweis ist einfach, und wir gehen hier nicht auf die Details ein. Der Schlüssel zum Schluss ist, dass es genauso viele Computerprogramme gibt, wie es beispielsweise natürliche Zahlen gibt.

Wiederholen:

Die Menge aller Zeichenketten über einem beliebigen Alphabet (z. B. Menge aller Computerprogramme) ist abzählbar.

Unzählig viele Sprachen

Was ist angesichts dieser Schlussfolgerung mit den Teilmengen dieser Zeichenfolgen? Anders gefragt, was ist mit der Menge aller Sprachen? Es stellt sich heraus, dass diese Menge nicht abzählbar ist.

Die Menge aller Sprachen über jedem Alphabet ist unzählbar.

Noch einmal, wir behandeln den Beweis hier nicht.

Konsequenzen

Obwohl sie nicht sofort offensichtlich sind, sind die Folgen der Unzählbarkeit von Sprachen und der Zählbarkeit der Menge aller Computerprogramme tiefgreifend.

Warum?

Angenommen, A ist der Satz von ASCII-Zeichen; ASCII-Zeichen sind genau die, die zum Erstellen eines Computerprogramms benötigt werden. Wir können sehen, dass die Menge der Strings, die beispielsweise JavaScript-Programme darstellen, eine Teilmenge von A* ist (hier ist * der Kleene-Sternoperator). Die Wahl von JavaScript ist willkürlich. Da diese Menge von Programmen eine Teilmenge einer zählbaren Menge ist, haben wir, dass die Menge von JavaScript-Programmen zählbar ist.

Lassen Sie uns außerdem bedenken, dass wir für jede Sprache L eine Funktion f definieren können, die 1 ergibt, wenn eine Zeichenfolge x in L ist, und ansonsten 0. Alle diese Funktionen sind verschieden. Da es eine 1:1-Korrespondenz mit der Menge aller Sprachen gibt und weil die Menge aller Sprachen überabzählbar ist, haben wir, dass die Menge aller solcher Funktionen überabzählbar ist.

Hier ist der grundlegende Punkt:

Da die Menge aller gültigen Programme abzählbar ist, die Menge der Funktionen aber nicht, muss es einige Funktionen geben, für die wir einfach keine Programme schreiben können.

Wir wissen noch nicht, wie diese Funktionen oder Probleme aussehen, aber wir wissen, dass es sie gibt. Das ist eine demütigende Erkenntnis, denn es gibt da draußen einige Probleme, für die es keine Lösung gibt. Wir halten Computer für extrem leistungsfähig und leistungsfähig, doch einige Dinge sind sogar für sie unerreichbar.

Nun stellt sich die Frage: „Wie sehen diese Probleme aus?“ Bevor wir mit der Beschreibung solcher Probleme fortfahren, müssen wir zunächst die Berechnung verallgemeinern.

Turing-Maschinen

Eines der allerersten mathematischen Modelle eines Computers wurde von Alan Turing entwickelt. Dieses Modell namens Turing-Maschine ist ein extrem einfaches Gerät, das unsere Vorstellung von Berechenbarkeit vollständig einfängt.

Die Eingabe in die Maschine ist ein Band, auf das die Eingabe geschrieben wurde. Unter Verwendung eines Lese-/Schreibkopfs wandelt die Maschine die Eingabe in einer Reihe von Schritten in eine Ausgabe um. Bei jedem Schritt wird entschieden, ob und was auf das Band geschrieben werden soll und ob es nach rechts oder links verschoben werden soll. Diese Entscheidung basiert auf genau zwei Dingen:

• Das aktuelle Symbol unter dem Kopf und

• Der interne Zustand der Maschine, der auch aktualisiert wird, wenn das Symbol geschrieben wird

Das ist es.

Universalität

1926 entwickelte Alan Turing nicht nur die Turing-Maschine, sondern hatte auch eine Reihe anderer wichtiger Einblicke in die Natur der Berechnung, als er seine berühmte Arbeit „On Computable Numbers“ schrieb. Er erkannte, dass ein Computerprogramm selbst als Eingabe für einen Computer betrachtet werden kann. Aus dieser Sichtweise hatte er die schöne Idee, dass eine Turing-Maschine diese Eingabe simulieren oder ausführen könnte.

Während wir diese Ideen heute für selbstverständlich halten, war die Idee einer solchen universellen Maschine zu Turings Zeiten der große Durchbruch, der es Turing ermöglichte, unlösbare Probleme zu entwickeln.

Church-Turing-These

Bevor wir fortfahren, lassen Sie uns einen wichtigen Punkt untersuchen: Wir wissen, dass die Turing-Maschine ein Berechnungsmodell ist, aber ist sie allgemein genug? Um diese Frage zu beantworten, wenden wir uns der Church-Turing-These zu, die folgende Aussage glaubhaft macht:

Alles Berechenbare ist von einer Turing-Maschine berechenbar.

Während Turing die Turing-Maschine als Berechnungsmodell entwickelte, entwickelte Alonzo Church auch ein Berechnungsmodell, das als Lambda-Kalkül bekannt ist. Diese Modelle sind leistungsfähig, weil sie beide Berechnungen beschreiben und dies in einer Weise tun, die jedem der heutigen Computer oder überhaupt jedem Computer aller Zeiten entspricht. Das bedeutet, dass wir eine Turing-Maschine verwenden können, um die unlösbaren Probleme zu beschreiben, nach denen wir suchen, in dem Wissen, dass unsere Ergebnisse für alle möglichen Computer in Vergangenheit, Gegenwart und darüber hinaus gelten würden.

Erkennbarkeit & Entscheidbarkeit

Wir müssen nur ein wenig mehr Hintergrund behandeln, bevor wir ein unlösbares Problem konkret beschreiben, nämlich die Konzepte von Spracherkennern und Sprachentscheidern.

Eine Sprache ist erkennbar, wenn es eine Turing-Maschine gibt, die sie erkennt.

und

Eine Sprache ist entscheidbar, wenn es eine Turing-Maschine gibt, die sie entscheidet.

Um eine Sprache zu erkennen, muss eine Turing-Maschine jeden String in der Sprache akzeptieren und darf nichts akzeptieren, was nicht in der Sprache ist. Es kann solche Zeichenfolgen ablehnen oder aufschleifen. Um ein Entscheider zu sein, muss eine Turing-Maschine bei ihrer Eingabe immer anhalten, entweder durch Akzeptieren oder durch Verwerfen.

Hier ist die Idee, bei der Eingabe anzuhalten, entscheidend. Tatsächlich sehen wir, dass Entscheider mächtiger sind als Erkenner. Außerdem ist ein Problem lösbar, oder anders ausgedrückt, eine Funktion ist nur dann entscheidbar, wenn es eine Turingmaschine gibt, die die durch die Funktion beschriebene Sprache entscheidet.

Unentscheidbarkeit

Wenn Sie jemals ein Computerprogramm geschrieben haben, kennen Sie sicherlich das Gefühl, dasitzen zu können und nur zuzusehen, wie der Computer seine Räder dreht, wenn das Programm ausgeführt wird. Sie wissen nicht, ob das Programm nur lange braucht oder ob ein Fehler im Code eine Endlosschleife verursacht. Sie haben sich vielleicht sogar gefragt, warum der Compiler den Code nicht überprüft, um festzustellen, ob er bei der Ausführung anhalten oder eine Endlosschleife ausführen würde.

Der Compiler hat eine solche Überprüfung nicht, weil es einfach nicht möglich ist. Es ist nicht so, dass Compiler-Ingenieure nicht schlau genug sind oder nicht über die nötigen Ressourcen verfügen; es ist einfach unmöglich, ein beliebiges Computerprogramm darauf zu überprüfen, ob es anhält.

Wir können dies mit der Turing-Maschine beweisen. Turingmaschinen kann man als Strings beschreiben, es gibt also eine abzählbare Anzahl davon. Angenommen, M ₁ , M ₂ und so weiter bilden die Menge aller Turing-Maschinen. Lassen Sie uns die folgende Funktion definieren:

Hier ist <M> die Syntax für „String-Codierung von M“, und diese Funktion stellt das Problem dar, 1 auszugeben, wenn M _i anhält, indem M _j als Eingabe akzeptiert und andernfalls 0 ausgegeben wird. Beachten Sie, dass M _i anhalten muss (dh ein Entscheider sein muss). Dies ist erforderlich, da wir eine unentscheidbare Funktion (dh ein unlösbares Problem) beschreiben wollen.

Lassen Sie uns nun auch eine Sprache L definieren, die aus Zeichenfolgencodierungen von Turing-Maschinen besteht, die KEINE eigenen Beschreibungen akzeptieren:

Beispielsweise kann eine Maschine M ₁ 0 am Eingang <M ₁ > ausgeben, während eine andere Maschine M ₂ 1 am Eingang <M ₂ > ausgeben kann. Um zu beweisen, dass diese Sprache unentscheidbar ist, fragen wir, was M _L , die Maschine, die die Sprache L bestimmt, tut, wenn ihr ihre eigene Beschreibung <M _L > als Eingabe gegeben wird. Es gibt zwei Möglichkeiten:

M _L akzeptiert <M _L >

oder

M _L lehnt <M _L > ab

Wenn M _L seine eigene Kodierung akzeptiert, bedeutet das, dass <M _L > nicht in der Sprache L ist; wenn dies jedoch der Fall wäre, dann hätte M _L seine Codierung überhaupt nicht akzeptieren sollen. Wenn andererseits M _L seine eigene Kodierung nicht akzeptiert, dann ist <M _L > in der Sprache L, also hätte M _L seine String-Kodierung akzeptieren sollen.

In beiden Fällen haben wir ein Paradoxon oder mathematisch ausgedrückt einen Widerspruch, der beweist, dass die Sprache L unentscheidbar ist; Damit haben wir unser erstes unlösbares Problem beschrieben.

Halteproblem

Während das gerade beschriebene Problem nicht relevant erscheint, kann es auf weitere unlösbare Probleme von praktischer Bedeutung reduziert werden, insbesondere das Halteproblem:

Die Sprache der Kodierungen von Turing-Maschinen, die auf der leeren Zeichenfolge anhalten.

Das Halteproblem betrifft die Frage, warum Compiler keine Endlosschleifen von früher erkennen können. Wenn wir nicht feststellen können, ob ein Programm mit dem leeren String endet, wie könnten wir dann möglicherweise feststellen, ob seine Ausführung zu einer Endlosschleife führen würde?

An diesem Punkt mag es so aussehen, als hätten wir nur mit den Händen herumgefuchtelt, um zu einer einfachen Schlussfolgerung zu gelangen. Wir haben jedoch festgestellt, dass keine Turing-Maschine sagen kann, ob ein Computerprogramm anhält oder für immer in einer Schleife bleibt. Dies ist ein wichtiges Problem für praktische Anwendungen und kann nicht auf einer Turing-Maschine oder einem anderen Computer gelöst werden. Ein iPhone kann dieses Problem nicht lösen. Ein Desktop mit vielen Kernen kann dieses Problem nicht lösen. Die Cloud kann dieses Problem nicht lösen. Selbst wenn jemand einen Quantencomputer erfinden würde, könnte er das Halteproblem noch nicht lösen.

Zusammenfassung

Bei unserer Untersuchung der Berechenbarkeitstheorie haben wir gesehen, dass es viele Funktionen gibt, die nicht im gewöhnlichen Sinne des Wortes durch ein Zählargument berechenbar sind. Wir haben genau definiert, was wir unter Berechnung verstehen, und sind bis zu Turings Inspiration aus seiner eigenen Erfahrung mit Stift und Papier zurückgegangen, um die Turing-Maschine zu formalisieren. Wir haben gesehen, wie dieses Modell alles berechnen kann, was jeder Computer heute oder für morgen in Aussicht stellen kann, und wir haben eine Klasse von Problemen erkannt, die überhaupt nicht berechenbar sind.

Dennoch hat die Berechenbarkeit einen Nachteil. Nur weil wir ein Problem lösen können, heißt das noch lange nicht, dass wir es auch schnell lösen können. Was nützt schließlich ein Computer, wenn seine Berechnungen nicht abgeschlossen sind, bevor die Sonne in zig Millionen Jahren in der Zukunft zu einer Nova auf uns wird?

Wir lassen berechenbare Funktionen und Sprachen hinter uns und besprechen nun die Komplexität von Berechnungen, untersuchen effiziente Berechnungen und das berühmte P vs. NP-Problem.

Komplexität

Langsam vs. schnell

Informatiker kennen eine Vielzahl von Klassen von Problemen, und zwei Klassen, die uns wichtig sind, umfassen Probleme, die Computer schnell oder effizient lösen können, bekannt als P , und Probleme, deren Lösungen schnell verifiziert werden können, aber nicht schnell erhalten werden können, bekannt als NP .

Angenommen, Sie sind für die Entwicklung von Algorithmen für einen Online-Partnervermittlungsdienst verantwortlich und jemand stellt die Frage: „Kann jeder ein Date bekommen?“ Die Antwort läuft darauf hinaus, kompatible Personen so zu koppeln, dass alle gekoppelt sind. Es stellt sich heraus, dass es effiziente Algorithmen gibt, um dieses Problem zu lösen. Dieses Problem liegt in der Menge P .

Nun, was wäre, wenn wir die größte Clique unter unseren Benutzern identifizieren wollten? Unter Clique verstehen wir das größte Netzwerk von Individuen, die alle miteinander kompatibel sind. Wenn die Benutzerzahl niedrig ist, kann dieses Problem schnell gelöst werden. Wir können beispielsweise eine Clique mit 3 Benutzern leicht identifizieren. Wenn wir jedoch anfangen, nach größeren Cliquen Ausschau zu halten, wird das Problem immer schwieriger zu lösen. Dieses Problem liegt in der Menge NP .

Formale Definitionen

P ist die Menge der Probleme, die in polynomieller Zeit lösbar sind. Das heißt, die Anzahl der Rechenschritte ist durch eine Polynomfunktion in Bezug auf die Problemgröße begrenzt. Wir wissen, dass die Frage „Kann jeder ein Date bekommen?“ Frage, auch bekannt als Bipartite-Matching-Problem, ist in P .

NP ist die Menge der Probleme, die in polynomieller Zeit verifizierbar sind. Dazu gehört natürlich jedes Problem in P; Wir wissen jedoch nicht, ob diese Eindämmung streng ist. Wir kennen Probleme, die effizient verifizierbar, aber nicht effizient lösbar sind, aber wir wissen nicht, ob das Problem wirklich hartnäckig ist. Das Cliquenproblem ist ein solches Problem. Wir wissen, dass wir die Lösung effizient verifizieren können, aber wir wissen nicht sicher, ob wir das Problem effizient lösen können.

Schließlich ist NP-vollständig die Menge von Problemen, die die schwierigsten Probleme in NP sind. Sie werden als die schwierigsten bezeichnet, da jedes Problem in NP effizient in NPC umgewandelt werden kann. Wenn also jemand eine effiziente Lösung für ein Problem in NPC finden würde, würde die gesamte Klasse von NP von P absorbiert. Das Cliquenproblem gibt es auch bei NPC .

Damit kommen wir zum Problem P vs. NP . Viele Informatiker und Mathematiker glauben fest daran, dass P und NP nicht gleich sind. Wenn sie es wären, wären die Auswirkungen mehr als tiefgreifend. Ein Großteil der heutigen digitalen Infrastruktur beruht auf der Tatsache, dass es in NP Probleme gibt, die in P nicht vorhanden sind. Wäre dies nicht der Fall, würden beispielsweise kryptografische Methoden über Nacht zusammenbrechen, sodass eine Person, die eine effiziente Lösung für ein NPC -Problem besitzt, selbst die strengsten Sicherheitsprotokolle unterlaufen kann.

Feinheiten der Lenkbarkeit

Für Informatikanfänger mag der Unterschied zwischen Matching- und Cliquenproblemen keine große Sache sein. Tatsächlich kann der Unterschied zwischen einem Problem in P und einem Problem in NP sehr subtil sein. Den Unterschied erkennen zu können, ist wichtig für jeden, der Algorithmen in der realen Welt entwickelt.

Betrachten Sie das Kürzeste-Wege-Problem. Bei zwei gegebenen Orten besteht das Ziel darin, den kürzesten Weg zwischen ihnen zu identifizieren. Ein iPhone berechnet dies in Millisekunden. Dies ist ein rechnerisch handhabbares Problem.

Betrachten Sie andererseits das Problem des Handlungsreisenden, bei dem das Ziel darin besteht, eine Teilmenge möglicher Ziele zu besuchen, die am Ursprungsort enden, während die kürzestmögliche Entfernung zurückgelegt wird. Dieses Problem ähnelt dem Kürzeste-Wege-Problem, ist aber NP-vollständig; es erklärt auch, warum die Supply-Chain-Logistik eine Milliarden-Dollar-Industrie ist.

Wir können sogar noch subtiler sein. Anstatt nach dem kürzesten Weg (P) zu fragen, können wir nach dem längsten Weg ohne Kreise fragen. Es stellt sich heraus, dass das Problem des längsten Pfads auch NP-vollständig ist.

Es gibt viele weitere Beispiele für diese subtile Unterscheidung, einschließlich der Identifizierung von Scheitelpunktabdeckungen in zweigeteilten vs. allgemeinen Graphen oder der Erfüllung boolescher Formeln mit zwei vs. drei Literalen pro Klausel. Der Punkt ist, dass es nicht sofort offensichtlich ist, ob ein Problem in P oder NP liegt, und deshalb ist die Laufzeitanalyse eine entscheidende Fähigkeit. Wenn der zu entwerfende Algorithmus für ein Problem in P ist, dann wissen wir, dass es eine effiziente Lösung gibt. Wenn andererseits das Problem in NP liegt, dann haben wir starke Argumente dagegen, eine Lösung zu verfolgen, weil der Algorithmus im Allgemeinen einfach zu lange brauchen würde, um das Problem zu lösen.

Zusammenfassung

In dieser Untersuchung der Komplexität haben wir die Problemklassen P und NP definiert. P stellt informell Probleme dar, die von einem Computer effizient gelöst werden können, während NP diejenigen darstellt, die effizient verifizierbar sind.

Niemand konnte beweisen, dass P ungleich NP ist. Ob diese beiden Klassen von Problemen äquivalent sind, ist als P vs. NP-Problem bekannt, und es ist heute das wichtigste offene Problem in der theoretischen Informatik, wenn nicht in der gesamten Mathematik. Tatsächlich hat das Clay Math Institute im Jahr 2000 das P vs. NP-Problem als eine der sieben wichtigsten offenen Fragen in der Mathematik bezeichnet und eine Millionen-Dollar-Prämie für einen Beweis ausgesetzt, der die Lösung dieses Problems bestimmt.

Fazit

In diesem Artikel haben wir uns mit den Bereichen Berechenbarkeit und Komplexität befasst und wichtige Fragen wie „Was ist ein Computer?“ beantwortet. Während die Details überwältigend sein können, gibt es eine Reihe von tiefgreifenden Erkenntnissen, an die es sich zu erinnern lohnt:

• Es gibt einige Dinge, die einfach nicht berechnet werden können, wie das Halteproblem.

• Es gibt einige Dinge, die nicht effizient berechnet werden können, wie die Probleme in NPC.

Wichtiger als die Details sind die Möglichkeiten, über Berechnungen und Berechnungsprobleme nachzudenken. In unserem Berufsleben und sogar in unserem Alltag können wir auf Probleme stoßen, die wir noch nie zuvor gesehen haben, und wir können bewährte Werkzeuge und Techniken anwenden, um die beste Vorgehensweise zu bestimmen.

Weiterführende Literatur im Toptal Engineering Blog:

• Wie man einen Dolmetscher von Grund auf neu schreibt