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

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?

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

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

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 )

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.