Schöne Ergebnisse in TCS

Kürzlich erwähnte ein Freund von mir (der in TCS arbeitet) in einem Gespräch, dass "er alle (oder so viel wie möglich) der schönen Ergebnisse in TCS in seinem Leben sehen / kennen wollte". Diese Art hat mich über die schönen Ergebnisse in diesem Bereich und damit die Motivation für die folgende Frage wundern lassen:

Welche Ergebnisse (oder Ideen) sind Ihrer Meinung nach in der theoretischen Informatik schön? Es wäre toll, wenn Sie auch den Grund nennen würden. [Wäre auch in Ordnung, wenn die Ideen aus der Mathematik stammen, aber Interesse geweckt und Verwendung in TCS gefunden hätten.]

Ich würde mit einer Antwort als Cantors diagonales Argument beginnen, weil es einfach, elegant und dennoch ein kraftvolles Ergebnis ist.

Die Unentscheidbarkeit des Halteproblems.

Aus vielen Gründen wunderschön. Es ist ein Unmöglichkeitsergebnis. Der Beweis verwendet eine Diagonalisierung. Die Aussage gilt für eine breite Palette von Rechenmodellen. Es kann auf verschiedene Arten formuliert werden, insbesondere unter Verwendung von Standard-Programmiersprachen. Es war ein Wendepunkt in der Geschichte des Rechnens. Die Erweiterung dieser Aussage führt zu Rices Theorem, Turing-Graden und vielen anderen coolen Ergebnissen. Etc. Etc. Etc.

Meiner Meinung nach ist die Curry-Howard-Korrespondenz eines der schönsten theoretischen Ergebnisse und das, was mich zu Nachforschungen veranlasst hat.

Die Vorstellung, dass zwei Systeme, Programme einerseits und Beweise andererseits, genau die gleiche Struktur haben, ist fast philosophischer Natur: Gibt es einige allgemeine "Argumentationsmuster"?

Die Möglichkeit der Kryptographie mit öffentlichen Schlüsseln, zum Beispiel das Diffie-Hellman-Schlüsselaustauschschema.

Es durchbricht das sehr starke Vorurteil, dass sich Menschen treffen müssen, bevor sie Geheimnisse auf einem unsicheren Kanal austauschen.

Ich war und bin immer noch überrascht von Euklids Algorithmus. Für mich ist es ein Beweis für Macht des menschlichen Denkens - , dass Menschen eines solchen Algorithmus vorstellen konnte so früh (um 300 vor Christus , wenn ich mein Gedächtnis vertrauen).

Schneller Vorlauf, es gibt stichhaltige Literatur zu diesem Thema. Ich denke, die Liste von Scott Aaronson sollte in dieser Hinsicht hilfreich sein - obwohl Aaronson selbst sagt, dass sie nicht vollständig (und nicht ganz theoretisch) ist.

Yaos Technik, von Neumanns Minmax-Theorem zu verwenden, um untere Schranken für randomisierte Algorithmen zu beweisen. Ich finde es als etwas nicht von dieser Welt.

Probabilistische Methode, um die Existenz von Objekten zu beweisen, die wir nur schwer konstruieren können, einschließlich des Lovasz Local Lemma. Diese Techniken sind so einfach und doch so mächtig.

Konstruktionen der Codierungstheorie von Madhu Sudan unter Verwendung von Polynomen.

Expander (dies begann als Ramanujan-Diagramme) und Extraktoren und ihre Anwendungen in der Pseudozufälligkeit.

Der Fast Fourier Transform-Algorithmus von Cooley und Tukey zum Auffinden der DFT. (Obwohl, wie von Tukey angenommen, dies eine Wiederentdeckung einer bekannten Technik war, die zumindest Gauß bekannt war!)

Der Satz von Barrington (ein sehr überraschendes Ergebnis seiner Zeit)

Satz der parallelen Wiederholung (obwohl das Ergebnis schön ist, ist der Beweis nicht einfach)

Lovasz-Theta-Funktion zur Schätzung der Shannon-Kapazität eines Graphen.

Ellipsoid-Algorithmus, der zeigte, dass LP in P ist, überraschend viele zu einer Zeit, als viele noch vermuteten, dass es NP-Complete sein könnte.

überraschenderweise eine der naheliegendsten noch nicht hinzugefügten Antworten. manchmal arbeitet man zu viel mit etwas, um es unparteiisch zu sehen. Die Theorie der NP-Vollständigkeit wurde von Cook / Levin auf den Weg gebracht und sofort von Karp verdeutlicht, der im Nachhinein noch vorsichtiger auf seine Allgegenwart hinwies. In vielerlei Hinsicht ist dies die Geburtsstunde der modernen TCS- und Komplexitätstheorie, und ihre Kern- / Schlüssel- / berüchtigte Frage P =? NP ist nach vier Jahrzehnten intensiven Studiums / Angriffs immer noch offen. P =? NP hat für seine Lösung einen Claymath-Preis in Höhe von 1 Mio. USD erhalten.

Mit dem Cook-Proof wurde der NDTM eingeführt, der anscheinend keine bloße theoretische Neugierde ist, sondern ein fast extrem grundlegender Bestandteil von TCS. hat sozusagen tausend Schiffe ins Leben gerufen. Darüber hinaus widersteht / trotzt es fortwährend den Bemühungen durch eine der anderen wichtigen / leistungsfähigen TCS-Techniken, die in dieser Liste aufgeführt sind, nämlich die Diagonalisierung, wie sie z Lösung, die auch durch das Razborov-Rudich Natural Proofs Paper (Godel-Preis 2007) vorgeschlagen / erweitert wurde.

Es gibt viele, viele Referenzen auf dem Subj, aber eine neuere mit einem Bericht aus erster Hand über die Geschichte kann in The P =? NP Question und Godels Lost Letter von RJ Lipton gefunden werden

Kolmogorov Komplexität und die Inkompressibilitätsmethode .

Die auf der Kolmogorov-Komplexität basierende Inkompressibilitätsmethode bot eine neue und intuitive Möglichkeit, Beweise zu formulieren. In einem typischen Beweis unter Verwendung der Inkomprimierbarkeitsmethode wählt man zuerst ein inkomprimierbares Objekt aus der diskutierten Klasse. Das Argument besagt immer, dass, wenn eine gewünschte Eigenschaft nicht gilt, das Objekt im Gegensatz zur Annahme komprimiert werden kann und dies den erforderlichen Widerspruch ergibt.

Siehe zum Beispiel den Beweis, dass es unendlich viele Primzahlen gibt, den alternativen Beweis des Gödelschen Unvollständigkeitssatzes oder die Verbindungen zwischen Kolmogorov-Komplexität und Computerkomplexität , ...

Ich war (und bin) erstaunt über Kleenes zweiten Rekursionssatz . Auf den ersten Blick scheint es einfach und nicht sehr nützlich zu sein, aber ich habe später herausgefunden, dass es sowohl mathematisch als auch philosophisch tiefgreifend ist.

Als ich auch über die auf Turing Machines bewährte Variante las (sehr informell, dass Maschinen ihre eigenen Beschreibungen erhalten können oder dass es Maschinen gibt, die ihre eigene Beschreibung ausgeben, wie ein Programm, das sich selbst druckt), spürte ich, wie sich mein Gehirn drehte so hart und doch fasziniert wie nie zuvor. Dann sehen Sie, wie der Satz verwendet wird, um einzeilige Beweise für die Unentscheidbarkeit des Halteproblems und die Nichterkennbarkeit minimaler Maschinen usw. zu liefern.

Shannons Satz zur Quellen- und Kanalcodierung.

Eine mathematische Definition, die zwischen Senden, Empfangen und Medium unterschied und die Semantik der Nachricht ignorierte, war ein großer Schritt. Entropie im Kontext von Daten ist ein fantastisch nützlicher Begriff. Und weil die Informationstheorie besser bekannt sein sollte.

Ein schönes Ergebnis, das auf dem PCP-Theorem aufbaut, besagt, dass es rechnerisch schwierig (NP-schwer) ist, mehr als 7/8 der Klauseln der 3SAT-Formel auch für erfüllbare zu erfüllen.

Shors-Algorithmus zum Faktorisieren in BQP . nach meiner meinung / erinnerung war die quantenberechnung bis zu diesem ergebnis im jahr 1994 eher eine theoretische kuriosität. an diesem punkt scheint das literatur- und forschungsinteresse am qm-rechnen explodiert zu sein. Es ist immer noch einer der wichtigsten bekannten QM-Algorithmen. 1999 mit dem Gödel-Preis ausgezeichnet. es zeigt sich auch, dass das Factoring in der QM-Berechnung in gewissem Sinne tatsächlich etwas besser verstanden wird als im klassischen Computing, wo z. B. die Frage, ob das Factoring NP-vollständig ist, noch offen ist.

Mir scheint, der AKS P-Zeit-Primalitätstest ist in verschiedener Hinsicht recht schön. Ein Durchbruch zu dieser Zeit, einer der großen, aber eher seltenen Durchbrüche in der Komplexitätstheorie in unseren Leben. Es löst ein Problem aus der griechischen Antike und bezieht sich auf einige der frühesten erfundenen Algorithmen (Eratosthensieb), dh die effiziente Identifizierung von Primzahlen. Es ist ein konstruktiver Beweis dafür, dass die Erkennung von Primzahlen in P erfolgt, im Gegensatz zu vielen großen Beweisen, die leider nicht konstruktiv sind.

Es ist mit dem in einer anderen Antwort erwähnten RSA-Kryptografiealgorithmus verbunden, da dieser Algorithmus große Primzahlen schnell finden muss, was vor dem AKS-Algorithmus nur wahrscheinlich möglich war. Es ist grundlegend mit der Zahlentheorie und anderen tiefen Problemen verbunden, z. B. der Riemannschen Vermutung, die in vielerlei Hinsicht das ursprüngliche Gebiet der Algorithmik ist.

Ausgezeichnet mit dem Gödel-Preis 2006 und dem Fulkerson-Preis 2006

Ich denke, der Graph-Minor-Satz von Robertson und Seymour war die wunderbarste Theorie, die ich je gesehen habe (und teilweise gelesen habe). Erstens ist es ziemlich kompliziert, aber Grundannahmen sind nicht schwer und können möglicherweise von jedem, der in TCS arbeitet, erraten werden. Ihre extreme Anstrengung, sie zu beweisen, war wunderbar. Tatsächlich verstehe ich die Kraft des menschlichen Geistes, nachdem ich einige der Artikel in dieser Reihe gelesen habe.

Auch der Graph-Minor-Satz hat einen großen Einfluss auf verschiedene Bereiche der TCS. Wie Graphentheorie, Approximationsalgorithmus, parametrisierte Algorithmen, Logik, ...

Eines meiner Lieblingsergebnisse ist, dass verschiedene Probleme scheinbar unendlicher Natur entscheidbar sind.

1. Die Theorie erster Ordnung von realen geschlossenen Feldern ist entscheidbar (von Tarski). Die euklidische Geometrie ist auch ein Modell der Axiome von real geschlossenen Feldern, daher sind nach Tarski Aussagen erster Ordnung in diesem Modell entscheidbar.
2. Presburger Arithmetik ist entscheidbar.
3. Die Theorie erster Ordnung von algebraisch geschlossenen Feldern (einschließlich komplexer Zahlen) ist entscheidbar.
4. Die monadische Logik zweiter Ordnung über unendlichen (und endlichen) Wörtern ist entscheidbar. Der Beweis ist elegant und kann Studenten beigebracht werden.

Es gibt viele schöne Ergebnisse über probabilistische Algorithmen, die täuschend einfach sind und einen großen Fortschritt in der Art und Weise darstellen, wie wir über Berechnungen nachdenken.

von Neumanns Trick, eine faire Münze mit einer voreingenommenen Münze umzusetzen. Wir sind so an probabilistische Algorithmen gewöhnt, aber von außen betrachtet ist dies unglaublich cool. Sowohl der Algorithmus als auch der Beweis sind für jeden zugänglich, der die Wahrscheinlichkeit der Highschool kennt.

Das Ergebnis von Tim Griffin, dass Operatoren wie call/ccdie klassische Logik steuern , erweitert die Curry-Howard-Korrespondenz.

call/cc$E$$\neg\neg \tau$$\mathtt{call/cc}{(E)}$$\tau$$\neg\tau$$\tau\rightarrow\bot$$\tau$

Sein Aufsatz "A Formulas-as-Types-Konzept der Kontrolle" erscheint in POPL 1990.

Mein Favorit ist Rabins linearer Zeitalgorithmus zur Berechnung des nächsten Punktpaares in der Ebene (oder genauer gesagt seiner Vereinfachung). Es wird die Bedeutung des Berechnungsmodells, die Leistungsfähigkeit randomisierter Algorithmen und eine elegante Art, über randomisierte Algorithmen nachzudenken, verdeutlicht.

Das heißt, CS ist noch weit davon entfernt, das Niveau an Eleganz zu erreichen, das man in der Mathematik vorfindet (nun, sie hatten 5000 Jahre Vorsprung), von grundlegenden Definitionen / Ergebnissen in der Analysis, Topologie (Fixpunktsätze), Kombinatorik, Geometrie (Pythagorasatz http : //en.wikipedia.org/wiki/File: Pythag_anim.gif ) usw.

Wenn Sie nach Schönheit suchen, suchen Sie überall danach ...

Dieses Ergebnis ist wahrscheinlich etwas neu, um als grundlegend eingestuft zu werden, aber ich glaube, dass die Interpretation der Typen als Homotopietypen geeignet ist. Diese Ansicht ermöglicht die Interpretation von Typen aus der konstruktiven Typentheorie als Mengen mit bestimmten geometrischen Eigenschaften, in diesem Fall der Homotopie .

Ich finde diese Sichtweise besonders schön, da sie bestimmte bisher komplexe Beobachtungen zur Typentheorie einfach macht, zum Beispiel die Tatsache, dass "Axiom K" nicht ableitbar ist .

Eine Übersicht über dieses aufstrebende Feld von Steve Awodey finden Sie hier .

Der wissensfreie Nachweis ist ein sehr interessantes Konzept. Es ermöglicht einer Entität, dem Prüfer, (mit hoher Wahrscheinlichkeit) einer anderen Entität, dem Prüfer, zu beweisen, dass sie "ein Geheimnis" kennt (eine Lösung für ein NP-Problem, eine modulare Quadratwurzel einer bestimmten Zahl, eine diskrete protokollieren Sie eine Nummer usw.), ohne Informationen über das Geheimnis zu geben (was auf den ersten Blick schwierig ist, da die erste Idee, um zu beweisen, dass Sie ein Geheimnis kennen, darin besteht, das Geheimnis tatsächlich zu verraten, und dass jede Kommunikation, die dazu führen könnte Der Prüfer, der glaubt, das Geheimnis zu kennen, kann a priori nur das Wissen des Prüfers über das Geheimnis erweitern.