Forcierungsmethode in Baker-Gill-Solovay Relativization Paper und Cohens Proof of Continuum Hypothesis Independence

15

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?

djkern
quelle
1
Wer weist darauf hin, dass es die gleiche Technik ist?
VZN

Antworten:

17

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:

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).

Joshua Grochow
quelle
9

Für die Verwendung von Forciertechniken in der Beweiskomplexität sollten Sie sich Folgendes ansehen:

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:

Kürzlich hat Jan Krajicek ein Buch veröffentlicht, in dem die folgenden Forciertechniken zusammengefasst sind:

Iddo Tzameret
quelle
Interessanter Sprung, aber hat noch niemand in Zeitungen / Büchern gesehen, der das Erzwingen tatsächlich mit dem Prinzip der Schublade / Beweisen vergleicht ...?
vzn 31.10.12
Das Pigeonhole-Prinzip ist hier der Name einer Aussage. Um zu zeigen, dass die Aussage von einer bestimmten Theorie unabhängig ist, verwendet man zwangsartige Konstruktionen. Die obigen Referenzen zeigen, wie das geht.
Iddo Tzameret
ok, aber Exponential-Size-Proofs von SAT mit Auflösung (via Pigeonhole-Konstruktionen) sind nicht "unabhängig", wie es scheint ... sie sind nur "groß" ... irgendwelche Online-Refs, die auf die Verbindung hinweisen? Ich gebe zu, ich bin ein bisschen überrascht, weil sich viele Refs auf Pigeonhole Proofs in SAT nicht auf "
Forcen
1
V0EINC0
1
(Forts.) Siehe dazu auch Jan Krajiceks Buch "Bounded Arithmetic, Propositional Logic, and Complexity Theory", Cambridge, 1995. Alle oben genannten Referenzen (ausgenommen das Buch von Krajicek aus dem Jahr 1995) sind online verfügbar. Der Zusammenhang mit dem Erzwingen ist beispielsweise in der obigen 2. Literaturstelle von Ajtai erläutert.
Iddo Tzameret
4

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.

Ideen beim Forcen haben die Komplexität der Berechnungen beeinflusst. Beispielsweise kann die Trennung von Komplexitätsklassen, die für ein Orakel relavitiert wurden (z. B. wie in BGS75), häufig als ressourcengebundene Versionen des Forcierens angesehen werden.

vzn
quelle