Wie erhält man eine "physische Intuition" für die Ergebnisse in TCS?

Es tut mir leid, wenn diese Frage etwas vage ist, aber ich bin gespannt, wie erfolgreich Forscher ein "Gefühl" für die Ergebnisse in TCS bekommen.

Beispielsweise kann die lineare Algebra geometrisch oder hinsichtlich ihrer physikalischen Interpretation (Eigenvektoren können als "stabile Punkte" in einem System angesehen werden) usw. verstanden werden. Es ist auch intuitiv, dass es ein IP-Protokoll für TQBF (als IP) gibt Das Protokoll kann als eine Art "Spiel" zwischen zwei Einheiten mit sehr unterschiedlicher Rechenleistung dargestellt werden. Ich stelle jedoch fest, dass viele der Ergebnisse, auch die extrem einfachen in TCS, keine so einfachen Intuitionen haben (MA AM). Schlimmer noch, gelegentlich werden unraffinierte Intuitionen furchtbar misstrauisch (2-SAT steht in P, während 3-SAT nicht in P steht (tatsächlich ist es NP-vollständig)). Gibt es "allgemeine Prinzipien" für die Entwicklung einer Intuition in TCS?$\subseteq$

Wie in vielen wissenschaftlichen Bereichen kann es Jahre dauern, bis die Intuition aufgebaut ist, aber es kann nur eine neue Idee erforderlich sein, um diese Intuition abzubauen (und hoffentlich wird etwas Schönes an seiner Stelle wieder aufgebaut).

Es gibt einige grundlegende Übungen, mit denen Sie versuchen können, die Intuition für eine Zeitung zu entwickeln, die Sie lesen und die nicht zu durchdringen scheinen. Hier ist eine, die ich von Zeit zu Zeit noch mache. Beginnen Sie mit einem Beweis, den Sie nicht verstehen, der aber sehr lang ist. Versuchen Sie, während Sie jeden Absatz des Beweises lesen, in eigenen Worten einen Satz darüber zu schreiben, was Ihrer Meinung nach in dem Absatz am Rand steht. Hoffentlich ist der Beweis gut genug geschrieben, dass es gut definierte "Teile" des Beweises gibt ("mache X, definiere dann eine neue Funktion f, wende dann X auf f an, ..."). Wenn nicht, trennen Sie den Beweis aus Ihren Sätzen in Ihre eigenen Teile.

$MA \subseteq AM$Ich würde so etwas wie "MAKE ARTHUR SPEAK MORE" sagen. Aber vielleicht scheint etwas anderes im Beweis die "Schlüsselidee" für Sie zu sein, was vollkommen in Ordnung ist. Es ist deine Intuition!)

Ich denke, mein Vorschlag ist für die meisten Mathematiker nützlich, aber ich fand ihn sehr nützlich für TCS, wo viele Beweise wirklich auf 1-2 wirklich neue Ideen hinauslaufen, und der Rest ist eine Synthese dieser Idee mit dem, was bereits bekannt war.

Sei vorsichtig mit deiner Intuition. Es hat viel Erfahrung, kann oft falsch und richtig zugleich sein und ist nicht einzigartig. Der Punkt ist, dass jeder seine eigene Intuition zu Problemen bringt, basierend auf seinen eigenen Komfortzonen, den Bedürfnissen des Problems und seinem Hintergrund. Wie Tsuyoshi betont, ist Intuition wirklich eine Menge harter Arbeit, die in ein paar prägnanten mentalen Bildern sublimiert wurde.

Mein Vorschlag wäre also: Arbeite einfach an Problemen, die dir Spaß machen, und versuche, deine eigenen Ideen zu entwickeln, auch wenn es noch andere gibt. So bauen Sie Ihre Intuition auf. Und wenn ein Ergebnis rätselhaft erscheint, bedeutet dies entweder, dass Sie es noch nicht ganz verstanden haben, oder es lauert irgendwo darunter ein einfacheres Ergebnis, das darauf wartet, entdeckt zu werden.

Da Sie Spiele als Beispiel für „physische Intuition“ betrachten, während ich in Spielen nichts mit Physik zu tun habe, gehe ich davon aus, dass Sie nicht auf „physische“, sondern auf „Intuition“ setzen.

Ich behaupte, dass ein Teil des Zwecks des Studiums (Ausbildung oder Forschung) in der theoretischen Informatik darin besteht , die Intuition für die abstrakten Begriffe zu entwickeln, die sich auf das Rechnen beziehen. Intuition wird erlangt, indem man das Konzept studiert und sich mit ihm vertraut macht. Ich erwarte nicht, dass es eine nette Abkürzung gibt.

Zum Beispiel werden Studenten im Grundstudium von der Unentscheidbarkeit des Stopp-Problems überrascht sein (wahrscheinlich, weil das bloße Vorhandensein einer unentscheidbaren Sprache bereits überraschend ist). Das Erlernen der Tatsache, ihres Beweises, einiger verwandter Ergebnisse und der breiten Anwendbarkeit der Beweistechnik macht dieses überraschende Ergebnis jedoch weniger überraschend und in der Tat sehr natürlich. Ich glaube, dass das Gleiche für kompliziertere Ergebnisse gilt.

Was das konkrete Ergebnis betrifft, stimme ich nicht zu, dass es für MA⊆AM keine einfache Intuition gibt. (Warnung: Ich studiere gerade dieses und ähnliche Ergebnisse selbst und sage möglicherweise etwas Falsches.) In einem MA-System muss Merlin eine einzige Antwort geben, die den meisten von Arthur verwendeten Zufallssequenzen entspricht. Wir ändern das System so, dass Arthur mehrere (polynomisch viele) Zufallssequenzen an Merlin sendet und Merlin eine einzige Antwort geben muss, die zu allen passt, was mir ein natürlicher Versuch erscheint. Der Nachweis der Solidität dieses AM-Systems ist eine einfache Anwendung des Chernoff-Verfahrens. Ich denke nicht, dass irgendetwas in diesem Ergebnis konzeptionell schwer zu verstehen ist.

Im Hintergrund: Ihre Frage erinnerte mich an einen schönen Blog-Beitrag „ Abstraktion, Intuition und der Irrtum des Monadentutorials “ von Brent Yorgey, in dem er die Schwierigkeit, die Intuition zu kommunizieren, durch eine fiktive Nichterklärung „Monaden sind Burritos“ erklärte. Wenn die obige Erklärung, wie der Beweis von MA⊆AM funktioniert, keinen Sinn ergibt, könnte ich den gleichen Irrtum demonstrieren. :(

Wenn Sie fünf Jahre Ihres Lebens damit verbringen, ein rein theoretisches Konzept X (z. B. ein bestimmtes esoterisches Rechenmodell) zu studieren, wird X schließlich zu einem natürlichen Bestandteil Ihres täglichen Lebens.

Sie lernen, wie sich X verhält, wie es sich anfühlt, wie es auf Ihre Manipulationen reagiert und in welcher Nachbarschaft es lebt. Sie erfahren, wer es entdeckt hat, wann und warum und was andere mit X erfolgreich oder erfolglos gemacht haben. Sie werden X genau so kennen, wie Sie jeden physischen Gegenstand kennen, dem Sie jeden Tag begegnen.

Sie wissen es vielleicht viel besser als diese seltsamen, schlecht definierten, unvorhersehbaren und unberechenbaren physischen Dinge ... Aber es ist ein langer Weg, und ich glaube nicht, dass es so viele magische Abkürzungen gibt.

Die Antworten hier decken bereits die meisten netten Vorschläge zur Intuition ab. Trotzdem würde ich noch eine geben, was nützlich ist, wenn Intuitionen während des Schreibens auf Papier entwickelt werden. Dies wird von meinem eigenen Lehrer, Hsueh-I Lu, vorgeschlagen, was ich sehr nützlich fand.

Wenn ein Ergebnis aufgeschrieben wird und die Richtigkeit überprüft zu werden scheint, schreiben Sie den gesamten Artikel neu . Dieses Mal haben wir erzwingen uns nicht irgendwelche Wörter oder Definitionen ähnlich wie die früheren Versionen zu verwenden. Das bringt uns dazu, ganz anders zu denken und neue Intuitionen zu entwickeln. Auch perturb alle Parameter in dem Papier verwendet wird , sehen , ob eine Reihe von Parametern von dem unterscheiden wir verwendeten ursprünglich noch funktioniert. Oft werden beim Umschreiben des Artikels einige Fehler aufgedeckt. Überlegen Sie sich neue Ideen, um sie zu überwinden.

Schließlich werden wir nach Umschreibungsrunden eine nette runde Vorstellung von unserem eigenen Ergebnis haben und werden nicht zu optimistisch / pessimistisch gegenüber der Kraft der neuen Ideen sein, die in der Zeitung vorgestellt werden, da wir es für einige versucht haben mal, und es ist klar, was funktioniert und was nicht.

Die gleiche Methode funktioniert, wenn Sie eine neue Zeitung lesen und mehr Intuitionen haben möchten als die, die Sie beim Lesen erhalten.

In meinem Fall sind die meisten TCS-Konzepte, von denen ich eine Ahnung habe, die ich anhand praktischer Ergebnisse erhalten habe. Wenn ich über Jahre hinweg das gleiche Modell oder den gleichen Algorithmus erfolgreich weiterentwickle und verwende, lenkt mich das immer mehr ab, bis ich herausfinde, warum der Algorithmus erfolgreich war. Dies gilt insbesondere dann, wenn es Zeit für ein Umschreiben ist - ich möchte wissen, was die TCS-Essenz der Sache ist, damit ich beim Refactoring nicht den magischen Staub verliere. Um all das herauszufinden, ist (für mich) normalerweise ein tiefer Rückblick auf das Jahr 1936 erforderlich, und ich muss in Beziehung setzen, was ich mit diesen Grundkonzepten gemacht habe. Ein Freund hat mir einmal geraten, "wie eine Turing-Maschine zu denken", als ich auf einem dieser Tauchgänge war, und dieser Rat ist mir geblieben.