Ich interessiere mich allgemein für die von Baker-Gill-Solovay und Cohen verwendete Forcierungsmethode. Ich suche nach so vielen Quellen, wie ich in Bezug auf die Technik selbst oder ihre Verwendung in die Hände bekommen kann. Hat jemand Vorschläge?
cc.complexity-theory
set-theory
djkern
quelle
quelle
Antworten:
Weitere Verwendungen des Forcierens (über sogenannte generische Orakel) in der Komplexitätstheorie finden Sie im Oracle Builder Toolkit ( frei erhältlich von Fortnows Homepage ) von Fenner, Fortnow, Kurtz und Li. Sie geben eine allgemeine Theorie der generischen Orakel und zeigen ihre vielfältigen Anwendungen in der Komplexität.
Wenn Sie daran interessiert sind, wie Orakel in der Komplexität Unabhängigkeitsbeweise in der Mengenlehre sind, interessieren Sie sich möglicherweise für die folgenden Artikel:
Arora, Impagliazzo, Vazirani. Relativierende versus nichtrelativierende Techniken: die Rolle der lokalen Überprüfbarkeit .
Impagliazzo, Kabanets, Kolokolova. Ein axiomatischer Ansatz zur Algebrisierung . ( Vollversion frei verfügbar von Kabanets Homepage )
Für die Verwendung des Forcierens in der Mengenlehre siehe das Buch Mengenlehre ( Mengenlehre bei Amazon ) von Jech, insbesondere Teile II und III des Buches (nicht zu verwechseln mit "Einführung in die Mengenlehre" von Hrbáček und Jech).
quelle
Für eine exzellente Einführung in das Forcen in der Mengenlehre gibt es Timothy Chows berühmten USENET-Post "Forcing for Dummies" sowie das formellere Paper "A beginner's guide to forcing" .
quelle
Für die Verwendung von Forciertechniken in der Beweiskomplexität sollten Sie sich Folgendes ansehen:
M. Ajtai. Die Komplexität des Pigeonhole-Prinzips . In Proceedings of the 29. jährlichen IEEE-Symposium über Grundlagen der Informatik, White Plains, NY, 1988, S. 346–355; und
M. Ajtai. Die Komplexität des Pigeonhole-Prinzips . Combinatorica 14 (1994), Nr. 4, 417–433.
Die Beweismethode ist ein arithmetisches Analogon des Forcierens (wie es bereits von Paris und Wilkie verwendet wird). Weitere kombinatorische (und verbesserte Untergrenzen) finden sich in J. Krajıcek, P. Pudlak und A. Woods, Exponential lower bounds to the size of bounded depth . 15–39. und T. Pitassi, PW Beame und R. Impagliazzo, Exponential lower bounds für das Pigeonhole-Prinzip , Comput. Complexity, 3 (1993), S. 97–140.
Siehe auch:
Soren Riis. Finitisierung in der gebundenen Arithmetik . 1994, BRICS, Institut für Informatik der Universität Aarhus.
Kürzlich hat Jan Krajicek ein Buch veröffentlicht, in dem die folgenden Forciertechniken zusammengefasst sind:
quelle
siehe auch Forcing in proof theory von Avigad, 30 Seiten, 2004. Er zitiert BGS75, aber nicht im Detail. Es gibt einige Hinweise auf Scott / Solovay als eine Umformulierung des Erzwingens in boolesche Modelle.
quelle