Gowers 'diskretisierter Borel-Bestimmungsansatz'

Gowers hat kürzlich ein Problem umrissen , das er "diskretisierte Borel-Determiniertheit" nennt und dessen Lösung mit dem Nachweis von Schaltkreisuntergrenzen zusammenhängt.

1. Können Sie einen Überblick über den Ansatz geben, der auf ein Publikum von Komplexitätstheoretikern zugeschnitten ist?

2. Was würde es brauchen, um mit diesem Ansatz irgendetwas zu beweisen , einschließlich des erneuten Nachweises bekannter Untergrenzen?

Lassen Sie mich einen Überblick über mein Verständnis der Motivation für den Ansatz geben. Seien Sie gewarnt, dass mir das Konzept der Borelschen Determiniertheit ziemlich neu ist und ich überhaupt kein Experte für Mengenlehre bin. Alle Fehler sind meine. Ich bin mir auch nicht sicher, ob das viel besser ist, als Gowers 'Beiträge zu lesen.

Ich denke, was Gowers im Sinn hat, ist kein endliches Analogon des Borel-Bestimmungssatzes, sondern ein endliches Analogon des Folgenden: Die Borel-Bestimmung folgt aus dem ZFC, während die Bestimmung von analytischen Spielen die Existenz von (im Wesentlichen) messbaren Kardinälen voraussetzt. Ich werde sehr kurz beschreiben, von welchen Spielen wir sprechen und was Borel-Determiniertheit ist, und dann werde ich dies mit dem Ansatz verbinden, untere Grenzen zu beweisen. Die Idee auf sehr hoher Ebene besteht darin, die Eigenschaft als eine Eigenschaft zu betrachten, die P \ poly von NP trennen kann.

Wir denken an Spiele, bei denen zwei Spieler I und II abwechselnd eine ganze Zahl "spielen". Das Spiel geht für immer weiter, also produzieren sie eine Sequenz . Das Spiel wird durch eine Gewinnmenge (dh eine Menge von Sequenzen) definiert. Wenn , gewinnt Spieler I, ansonsten gewinnt Spieler II.$x= x_1, x_2, \ldots$$A \subseteq \mathbb{N}^\mathbb{N}$$x \in A$

Ein Spiel wird bestimmt, wenn entweder Spieler I oder Spieler II eine Gewinnstrategie haben: eine Möglichkeit, basierend auf dem bisherigen Spiel einen nächsten Zug zu entscheiden, der einen Gewinn garantiert. Es stellt sich heraus, dass alle Spiele enge Verbindungen zu den Grundlagen der Mengenlehre aufweisen (dies ist jedoch nicht der Fall, wenn Sie an das Axiom der Wahl glauben). In jedem Fall ist ein einfaches Beispiel, wenn Spiele tatsächlich bestimmt werden, wenn in der Produkttopologie auf geöffnet ist , was eine originelle Art zu sagen ist, dass die Mitgliedschaft kann entschieden nur auf der Grundlage einer endlichen Anzahl von Elementen von . Zum Beispiel ist das Spiel, in dem ich gewinne, wenn sie als erste eine gerade Zahl spielt, offen. Ein weiteres einfaches Beispiel für bestimmte Spiele sind geschlossene Spiele, dh Spiele, bei denen$A$$\mathbb{N}^\mathbb{N}$$x \in A$$x$$x \not \in A$ kann aufgrund einer endlichen Teilfolge von . Geschlossene Spiele sind offene Spiele, bei denen die Rollen der Spieler vertauscht sind.$x$

Jetzt können wir zur Borel-Determiniertheit kommen, und gleich danach werde ich versuchen, dies mit Schaltkreisen und Komplexität in Verbindung zu bringen. Eine Borel-Menge ist eine Menge, die aus offenen und geschlossenen Mengen abgeleitet werden kann, indem wiederholt eine abzählbare Anzahl von Vereinigungen und Kreuzungen angewendet wird. Sie sollten offene und geschlossene Mengen als Ihre Grundmengen und Borel-Mengen als von Grundmengen abgeleitete Mengen betrachten, die mehrere Ebenen mit einer "kleinen" (= abzählbaren) Anzahl von einfachen Operationen in jeder Ebene verwenden. Es stellt sich heraus, dass Sie in ZFC nachweisen können, dass Borel-Sätze bestimmt sind, und dass dies genau das Beste ist, was Sie tun können.

Die Analogie, die Gowers hier zieht, ist, dass Borel-Sets wie kleine Schaltkreise sind. In der endlichen Welt ersetzen wir das "Universum" durch den Hypercube . Unsere Grundmengen werden zu Facetten des Würfels: für ; diese entsprechen den Literalen und . Sie können UND und ODER von Literalen als Vereinigungen und Schnittpunkte solcher Mengen schreiben. Für eine boolesche Funktion ist es also möglich, aus Vereinigungen und Schnittpunkten von Grundmengen zu erzeugen entspricht einer Größe$\mathbb{N}^\mathbb{N}$$\{0,1\}^n$$\{x \in \{0,1\}^n: x_i = b\}$$b \in \{0,1\}$$x_i$$\bar{x}_i$$f:\{0,1\}^n \rightarrow \{0,1\}$$f^{-1}(1)$$s$$s$Schaltung für .$f$

Lassen Sie mich ein Wort über analytische Mengen werfen. Eine analytische Menge ist eine Projektion einer Borelmenge: Wenn eine Borelmenge ist, dann ist analytisch. Durch unsere Korrespondenz zwischen Borel-Mengen und Funktionen mit geringer Schaltungskomplexität sind analytische Mengen wie NP / Poly.T = { x : ≤ y ( x , y ) ≤ S $S \subseteq X \times Y$$T = \{x: \exists y\ (x,y) \in S\}$

Nun lässt er sich von einem Beweis der Borelschen Bestimmtheit inspirieren, eine Eigenschaft (im Sinne von Razborov-Rudich) zu entwickeln, mit der Funktionen mit kleiner Schaltungskomplexität von Funktionen mit großer Schaltungskomplexität unterschieden werden können. Die Hoffnung ist natürlich, dass die Immobilie die natürliche Beweisbarriere umgeht.

Martins Beweis für die Bestimmtheit von Borel basiert auf einem konzeptionell sehr übersichtlichen Ansatz: Martin zeigt, dass jedes Borel-Spiel das Bild eines offenen (in der Tat geschlossenen) Spiels unter einer Map , also$\pi$$\pi$bewahrt Gewinnstrategien - nennen wir dies einen "Lift". Was Martin also zeigt, ist, dass jedes Borel-Spiel das Bild eines Spiels ist, in dem das Gewinnset ein Grundset ist. Da es leicht ersichtlich ist, dass offene Spiele bestimmt werden, beweist dies die Borel-Determiniertheit. Der Beweis ist induktiv, wobei der Basisfall zeigt, dass geschlossene Spiele aufgehoben werden können. Der wichtige Teil ist, dass jeder Schritt der Induktion das Universum "in die Luft jagt": Um ein Level der Borel-Mengen-Konstruktion loszuwerden, muss ein Spiel zu einem Spiel über ein Universum gehoben werden, das im Wesentlichen die Kraftmenge des Universums des Originalspiels ist . Interessanterweise ist dies unvermeidlich: Borel-Sets, für deren Definition mehr Ebenen erforderlich sind, können nur in Spielen über viel größere Universen hinweg gehoben werden. Analytische Mengen erfordern Universen, die so groß sind, dass ihre Existenz große Kardinalaxiome erfordert.

Gowers lässt sich davon inspirieren und formuliert ein Spiel, in dem Spieler I und Spieler II gemeinsam ein spezifizieren müssen . Spieler I gewinnt, wenn , ansonsten gewinnt Spieler II. Spieler I kann die erste Hälfte der Koordinaten angeben und Spieler II die zweite Hälfte. Die Intuition ist nun, dass Spiele, die einfachem , dh mit geringer Schaltungskomplexität, einen Martin-ähnlichen Aufstieg in ein relativ kleines Universum ermöglichen sollten, genau wie es Borel-Spiele tun. Andererseits sollte zufälliges Universen mit doppelter Exponentialgröße erfordern, und hoffentlich sollte es auch NP-hartes sein, weil sie analytischen Spielen entsprechen würden.f ( x ) = 1 f f f $x$$f(x) = 1$$f$$f$$f$$f$

Lassen Sie mich etwas konkreter darauf eingehen, was ein Aufzug im Martin-Stil ist, aber überprüfen Sie die Gowers-Stellen auf technische Definitionen. Ein Lift im Martin-Stil (in der Gowers-Terminologie "Ramsey") ist ein Lift für ein Spiel, bei dem einige koordinatenweise angegeben werden, wobei das Universum ist und möglicherweise größer als , aber jetzt der Gewinner ist Die Bedingung ist sehr einfach: Ob Spieler I oder II gewinnt, hängt vom Wert einer einzelnen Koordinate von . Wie in Martins Beweis, muss ein Aufzug Gewinnstrategien bewahren.U 2 n$y \in U$$U$$2^n$$y$

Die Hoffnung, dass dies die natürliche Beweisbarriere umgeht, basiert auf der Intuition, dass die Liegenschaft "Martin-Stil-Auftrieb in ein kleines Universum hat", ist wahrscheinlich nicht einfach zu berechnen. Aber zu diesem Zeitpunkt ist es nicht klar, ob die Paritätsfunktion einen Auftrieb zu einem kleinen Universum hat. Ich mache mir Sorgen, dass die entsprechende Analogie zu Borel-Mengen die Funktionen in AC0 sein könnte: Wenn man einen kleinen Lift für die Parität findet, würde sich zumindest diese Sorge lindern.$f$