Metoda wymuszania zastosowana w pracy relatywizacyjnej Bakera-Gilla-Solovaya i dowód hipotezy Cohena na temat ciągłości niezależności

15

Ogólnie interesuje mnie metoda wymuszania stosowana przez Baker-Gill-Solovay i Cohen. Szukam tak wielu źródeł, jak tylko mogę uzyskać informacje na temat samej techniki lub jej zastosowania. Czy ktoś ma jakieś sugestie?

cc.complexity-theory set-theory

— djkern
źródło

1

kto wskazuje, że to ta sama technika?

— vzn

17

Więcej zastosowań wymuszania (za pomocą tak zwanych wyroczni ogólnych) w teorii złożoności znajduje się w Zestawie narzędzi Oracle Builder's Toolkit ( bezpłatnie dostępnym ze strony głównej Fortnowa ) autorstwa Fennera, Fortnowa, Kurtza i Li. Podają ogólną teorię ogólnych wyroczni i pokazują złożoność jej licznych zastosowań.

Jeśli interesuje Cię, jak wyrocznie w złożoności są jak dowody niezależności w teorii mnogości, możesz zainteresować się następującymi artykułami:

Arora, Impagliazzo, Vazirani. Techniki relatywizacyjne a nierelatywistyczne: rola lokalnej checkowalności .
Impagliazzo, Kabanets, Kolokolova. Podejście aksjomatyczne do algebriacji . ( pełna wersja dostępna bezpłatnie ze strony głównej Kabanets )

Zastosowania wymuszania w teorii mnogości znajdują się w książce Teoria mnogości ( Set Theory on Amazon ) Jecha, zwłaszcza w części II i III tej książki (nie mylić z „Wstępem do teorii mnogości” Hrbáčka i Jecha).

— Joshua Grochow
źródło

11

Doskonałe wprowadzenie do wymuszania teorii mnogości zawiera słynny post Timothy'ego Chowa USENET „Forcing for dummies”, a także bardziej formalny dokument, który z niego powstał, „Przewodnik dla początkujących dotyczący wymuszania” .

— arnab
źródło

9

W przypadku zastosowań wymuszania podobnych technik w dowodowej złożoności warto przyjrzeć się:

M. Ajtai. Złożoność zasady szufladki . W materiałach z 29. dorocznego sympozjum IEEE na temat podstaw informatyki, White Plains, NY, 1988, s. 346–355; i
M. Ajtai. Złożoność zasady szufladki . Combinatorica 14 (1994), no. 4, 417–433.

Metoda dowodu jest arytmetycznym analogiem wymuszania (takiego, jakiego używali już Paris i Wilkie). Bardziej kombinatoryczne (i ulepszone dolne granice) znajdują się w J. Krajıcek, P. Pudlak i A. Woods, Wykładnicze dolne granice do wielkości ograniczonej głębokości Dowody Frege'a zasady szufladki , Random Structures Al Algorytmy, 7 (1995), s. 15–39. oraz T. Pitassi, PW Beame i R. Impagliazzo, wykładnicze dolne granice dla zasady szuflady, Comput. Complexity, 3 (1993), s. 97–140.

Zobacz też:

$p$
Soren Riis. Zakończenie w arytmetyki ograniczonej . 1994, BRICS, Wydział Informatyki Uniwersytetu w Aarhus.

Niedawno Jan Krajicek opublikował książkę jednoczącą te techniki wymuszania:

J. Krajicek. Wymuszanie przy użyciu zmiennych losowych i złożoności dowodu . Cambridge University Press, grudzień 2010. ( Szkic dostępny ze strony domowej Krajicka )

— Iddo Tzameret
źródło

ciekawy skok, ale nie widziałem nikogo w gazetach / książkach, który faktycznie porównywałby zmuszanie do zasady / dowodów szuflady ...?

— vzn

Zasada Pigeonhole tutaj jest nazwą stwierdzenia. Aby pokazać, że stwierdzenie jest niezależne od pewnej teorii, używa się konstrukcji przypominających forsowanie. Powyższe odniesienia pokazują, jak to zrobić.

— Iddo Tzameret,

ok, ale wykładnicze dowody wielkości SAT wykorzystujące rozdzielczość (za pośrednictwem konstrukcji szuflad) nie wydają się „niezależne”, wydaje się… są po prostu „duże” ... jakieś referencje online wskazujące połączenie? przyznaję, że jestem trochę zaskoczony, ponieważ wiele referencji dotyczących dowodów na szufladę w SAT nie odnosi się do „wymuszania” ....

— 1'12

1

V^{0}

$V^0$

A C^{0}

$AC^0$

1

(cd.) Zobacz także na ten temat książkę Jana Krajicka „Arytmetyka ograniczona, logika zdań i teoria złożoności”, Cambridge, 1995. Wszystkie powyższe odniesienia (z wyjątkiem książki Krajicka z 1995 r.) Są dostępne on-line. Związek z wymuszaniem wyjaśniono np. W drugim odnośniku do Ajtai powyżej.

— Iddo Tzameret,

4

patrz także Forcing in teorii teorii Avigada, 30 pp, 2004. cytuje BGS75, ale nie szczegółowo. istnieje odniesienie do Scotta / Solovay'a jako zmiany w zmuszaniu do modelowania wartości boolowskich.

Pomysły wymuszania miały wpływ na złożoność obliczeniową; na przykład oddzielenie klas złożoności zrewitalizowanych w wyroczni (np. jak w BGS75) często można postrzegać jako ograniczone do zasobów wersje wymuszania.

— vzn
źródło