Podejście Gowersa do „dyskretnej determinacji Borela”

Gowers przedstawił ostatnio problem, który nazywa „dyskretną determinacją Borela”, którego rozwiązanie dotyczy dolnych granic obwodu dowodzenia.

1. Czy możesz podać podsumowanie podejścia, które jest dostosowane do grupy teoretyków złożoności?

2. Co potrzeba, aby to podejście wykazało cokolwiek , w tym ponowne udowodnienie znanych dolnych granic?

Pozwól, że przedstawię podsumowanie mojego rozumienia motywacji tego podejścia. Ostrzegam, że jestem dość nowy w koncepcji determinacji Borela i wcale nie jestem ekspertem w teorii mnogości. Wszystkie błędy są moje. Nie jestem też pewien, czyta to wszystko o wiele lepiej niż czytanie postów Gowersa.

Myślę, że to, co Gowers ma na myśli, nie jest skończonym analogiem twierdzenia o determinacji Borela, ale skończonym analogiem następującego: determinacja Borela wynika z ZFC, podczas gdy determinacja gier analitycznych wymaga istnienia (zasadniczo) mierzalnych kardynałów. Bardzo krótko opiszę, o których grach mówimy i czym jest determinacja Borela, a następnie połączę to z podejściem do udowodnienia niższych granic. Bardzo wysokim pomysłem jest uznanie, że właściwość „pozwala na działanie analogu finalnego dowodu determinacji Borela” jako właściwość, która może oddzielić P \ poli od NP.

Myślimy o grach, w których dwóch graczy I i II kolejno „grają” liczbą całkowitą. Gra trwa wiecznie, więc tworzą sekwencję . Grę określa zwycięski zestaw A ⊆ N N (tj. Zestaw sekwencji). Jeśli x ∈ A, to gracz I wygrywa, w przeciwnym razie gracz II wygrywa.$x= x_1, x_2, \ldots$$A \subseteq \mathbb{N}^\mathbb{N}$$x \in A$

Gra jest ustalana, czy gracz I lub gracz II ma strategię wygrywania: sposób decydowania o kolejnym ruchu na podstawie dotychczasowej gry, który gwarantuje zwycięstwo. To, czy wszystkie gry są określone, okazuje się mieć bliskie związki z podstawami teorii mnogości (nie są, jeśli wierzysz w wybrany aksjomat). W każdym razie jednym prostym przykładem, w którym gry są faktycznie ustalane, jest otwarcie w topologii produktu na N N , co jest fantazyjnym sposobem stwierdzenia, że ​​członkostwo x ∈ A może być ustalone tylko na podstawie skończonej liczby elementów $A$$\mathbb{N}^\mathbb{N}$$x \in A$$x$. Na przykład gra, w której gracz I wygrywa, jeśli ona pierwsza zagra parzystą liczbę, jest otwarta. Innym prostym przykładem określonych gier są gry zamknięte, tj. Gry, w których można ustalić na podstawie skończonej podsekwencji $x \not \in A$$x$ . Gry zamknięte to gry otwarte, w których role graczy są odwrócone.

Teraz możemy dojść do determinacji Borela, a zaraz po tym spróbuję powiązać to z obwodami i złożonością. Zestaw Borela to zbiór, który można uzyskać z zbiorów otwartych i zamkniętych poprzez wielokrotne stosowanie policzalnej liczby połączeń i skrzyżowań. Powinieneś myśleć o zestawach otwartym i zamkniętym jako o zestawach podstawowych, a zestawy Borela wyprowadzone z zestawów podstawowych przy użyciu kilku poziomów „małej” (= policzalnej) liczby prostych operacji na każdym poziomie. Okazuje się, że możesz udowodnić w ZFC, że zestawy Borela są określone, i istnieje precyzyjne poczucie, że jest to najlepsze, co możesz zrobić.

Analogia, którą, jak sądzę, rysuje tutaj Gowers, jest taka, że ​​zestawy Borela są jak małe obwody. W skończonym świecie zastępujemy „wszechświat” hipersześcianem { 0 , 1 } n . Nasze podstawowe zestawy stają się aspektami kostki: { x ∈ { 0 , 1 } n : x i = b } dla b ∈ { 0 , 1 } ; są równoważne literałach x I i ˉ x$\mathbb{N}^\mathbb{N}$$\{0,1\}^n$$\{x \in \{0,1\}^n: x_i = b\}$$b \in \{0,1\}$$x_i$$\bar{x}_i$. Możesz pisać AND i OR literałów jako związki i przecięcia takich zbiorów. Tak więc, dla logicznych funkcji , jest w stanie wytworzyć M - 1 ( 1 ) z s związków i skrzyżowań podstawowych zestawów odpowiada mający wielkość s obwód f .$f:\{0,1\}^n \rightarrow \{0,1\}$$f^{-1}(1)$$s$$s$$f$

Pozwól, że dodam słowo o zestawach analitycznych. Zbiór analityczny jest rzutem zbioru Borela: jeśli jest zbiorem Borela, to T = { x : ∃ y ( x , y ) ∈ S } jest analityczny. Dzięki naszej zgodności między zestawami Borela a funkcjami złożoności małych obwodów, zestawy analityczne są jak NP / poly.$S \subseteq X \times Y$$T = \{x: \exists y\ (x,y) \in S\}$

Teraz czerpie inspirację z dowodu determinacji Borela, aby wymyślić właściwość (w sensie Razborova-Rudicha) do odróżnienia funkcji złożoności małego obwodu od funkcji złożoności dużego obwodu. Oczywiście istnieje nadzieja, że ​​nieruchomość ominie barierę naturalnych dowodów.

Dowód Martina na określenie determinacji Borela wykorzystuje koncepcyjnie bardzo schludne podejście: Martin pokazuje, że każda gra Borela jest obrazem otwartej (w rzeczywistości clopen) gry pod mapą , tak że $\pi$$\pi$zachowuje zwycięskie strategie - nazwijmy to „windą”. Martin pokazuje więc, że każda gra Borel jest obrazem gry, w której zwycięski zestaw jest zestawem podstawowym. Ponieważ otwarte gry można łatwo ustalić, świadczy to o determinacji Borela. Dowód jest indukcyjny, a podstawa pokazuje, że zamknięte gry można podnieść. Ważną częścią jest to, że każdy etap indukcji „wysadza” wszechświat: pozbycie się jednego poziomu konstrukcji zestawu Borela wymaga podniesienia gry do gry nad wszechświatem, który jest zasadniczo zestawem mocy wszechświata oryginalnej gry . Co ciekawe, jest to nieuniknione: zestawy Borela, które wymagają zdefiniowania większej liczby poziomów, można przenieść tylko do gier w znacznie większych wszechświatach. Zestawy analityczne wymagają wszechświatów, które są tak duże, że ich istnienie wymaga dużych kardynalnych aksjomatów.

$x$$f(x) = 1$$f$$f$$f$$f$

$y \in U$$U$$2^n$$y$ . Podobnie jak w dowodzie Martina, winda musi zachować zwycięskie strategie.

$f$