Gibt es Referenzen (online oder in Buchform), die TCS-Theoreme nach Beweisverfahren organisieren und diskutieren? Garey und Johnson tun dies für die verschiedenen Arten von Widget-Konstruktionen, die für NP-Vollständigkeits-Proofs benötigt werden (insbesondere in Kapitel 3 ihres Buches), aber ich frage mich, ob es etwas gibt, das die Proof-Techniken in TCS umfassender behandelt.
So könnten Themen beispielsweise die Diagonalisierung sein, die weiter nach der Art der verwendeten Konstruktion aufgeschlüsselt ist. Beweise durch Berechnungsgeschichten; Tableau-Konstruktionen; Inkomprimierbarkeitsargumente usw. Ich schätze, ich könnte einfach eine Standardtheorie des Berechnungstextes zerlegen und die Abschnitte neu anordnen, aber es wäre großartig, wenn es etwas gibt, das auch einige zusätzliche Kommentare liefert und zeigt, wo Gemeinsamkeiten zwischen den Techniken bestehen gebraucht.
Nur um klar zu sein, da jeder Text wird verwenden Beweise, was ich wirklich in Erkenntnis interessiert ist ein Hinweis , wo die Beweistechniken selbst der eigentliche Gegenstand sind.
Zusätzlich zu Kapitel 3 von Garey und Johnson ist mir noch ein Teilbeispiel eingefallen : In Li und Vitanyi wird in Kapitel 6 die Inkompressibilitätsmethode erörtert und es werden Beispiele für die Anwendung der Technik gegeben.
Antworten:
Der Complexity Theory Companion von Hemaspaandra und Ogihara . Es ist nicht erschöpfend in Bezug auf Techniken (ich vermute, kein solches Buch ist es), aber ich denke, es ist eine Antwort auf Ihre Frage. Hier sind die Titel der Kapitel:
quelle
Hier ist ein weiteres Buch, in dem die Kapitel sich mehr auf Beweistechniken konzentrieren.
"Extremale Kombinatorik mit Anwendungen in der Informatik", von Stasys Jukna. Es ist ein schönes Buch und deckt eine Menge Kombinatorik ab, die Sie möglicherweise in TCS benötigen. Selbstverständlich werden keine Diagonalisierungen, Tableaus usw. behandelt, aber es handelt sich um eine Sammlung übersichtlicher kombinatorischer Techniken, die nach einer Anwendung suchen (und an verschiedenen Stellen im Text werden Anwendungen beschrieben).
Ein "früher Entwurf" der zweiten Ausgabe ist hier verfügbar .
quelle
Sanjeev Arora hat eine gute Sammlung von Notizen, die er "A Theorist's Toolkit" nennt.
quelle
Das Buch "Gems of Theoretical Computer Science" ist ein guter Weg, um viele verschiedene Techniken zu lernen (obwohl Sie jede nur einmal anwenden sehen):
http://www.calvin.edu/~rpruim/publications/gems/
quelle
Es gibt ein Wiki, das verschiedenen Beweistechniken gewidmet ist: http://www.tricki.org/ (scheint von Timothy Gowers inspiriert zu sein).
quelle
Weitere Techniken, die in vielen Bereichen der theoretischen Informatik nützlich sind:
Noga Alon und Joel H. Spencer, The Probabilistic Method (3. Auflage), Wiley, ISBN 0470170204.
quelle
S. Fenner, L. Fortnow, S. Kurtz und L. Li. Toolkit eines Orakelbauers. Information and Computation, 182 (2): 95-136, 2003. (auch auf der Homepage von Lance erhältlich ).
Dies ist im Grunde ein Übersichtsartikel über die Verwendung von Generizität bei der Konstruktion von "Designer-Orakeln" (dh Orakeln, die verschiedene Eigenschaften haben sollen). Obwohl es sich um ein Papier handelt, ist es meiner Meinung nach eine Antwort auf die Frage, da es sich eher auf die Technik und ihre Verwendung als auf ein bestimmtes Ergebnis konzentriert. [Dies ist jedoch viel spezifischer als der Complexity Theory Companion, weshalb ich dachte, dass dies in einer separaten Antwort erfolgen sollte.]
quelle
Wir haben einige Referenzfragen zu cs.SE gestartet, die typische (bisher einführende) TCS-Probleme behandeln. Neben der allgemeinen Relevanz enthalten einige Antworten Methoden, die möglicherweise nicht jedem Forscher bekannt sind, z.
Wir haben auch, wie man P = NP nicht löst? Das ist mehr über Anti-Techniken.
quelle
Ganz im Sinne von Sanjeev Aroras Notizen, die @umar gepostet hat, mag ich Madhur Tulsianis Vorlesungsnotizen und Übungen für seine "Mathematical Toolkit" -Klasse, die auf der Webseite des Kurses veröffentlicht wurde . Zusätzlich zu Aroras exzellentem Material bieten seine Notizen eine gute Abdeckung der Spektralgraphentheorie sowie der Aktualisierungsmethode für multiplikative Gewichte.
quelle