Enfoque de Gowers "determinación de Borel discretizada"

Gowers ha esbozado recientemente un problema, que él llama "determinación Borel discreta", cuya solución está relacionada con probar los límites inferiores del circuito.

1. ¿Puede proporcionar un resumen del enfoque que se adapta a una audiencia de teóricos de la complejidad?

2. ¿Qué se necesitaría para que este enfoque demuestre algo , incluyendo volver a probar los límites inferiores conocidos?

Permítanme dar un resumen de mi comprensión de la motivación para el enfoque. Tenga en cuenta que soy bastante nuevo en el concepto de determinación de Borel, y no soy un experto en teoría de conjuntos. Todos los errores son míos. Además, no estoy seguro de leer esto es mucho mejor que leer las publicaciones de Gowers.

Creo que lo que Gowers tiene en mente no es un análogo finitario del teorema de determinación de Borel, sino un análogo finitario de lo siguiente: la determinación de Borel se deriva de ZFC, mientras que la determinación de juegos analíticos requiere la existencia de (esencialmente) cardinales medibles. Describiré muy brevemente de qué juegos estamos hablando y cuál es la determinación de Borel, y luego vincularé esto con el enfoque para probar los límites inferiores. La idea de muy alto nivel es considerar que la propiedad "permite que funcione un análogo finitario de una prueba de determinación de Borel" como una propiedad que puede separar P \ poly de NP.

Pensamos en juegos donde dos jugadores I y II se turnan para "jugar" un número entero. El juego continúa para siempre, por lo que producen una secuencia . El juego se define por un conjunto ganador A ⊆ N N (es decir, un conjunto de secuencias). Si x ∈ A entonces el jugador I gana, de lo contrario gana el jugador II.$x= x_1, x_2, \ldots$$A \subseteq \mathbb{N}^\mathbb{N}$$x \in A$

Un juego se determina si el jugador I o el jugador II tienen una estrategia ganadora: una forma de decidir un próximo movimiento basado en el juego hasta el momento que garantiza una victoria. Si todos los juegos están determinados resulta tener conexiones íntimas con los fundamentos de la teoría de conjuntos (no lo son, si crees en el axioma de elección). En cualquier caso, un ejemplo simple cuando los juegos se determinan es cuando está abierto en la topología del producto en N N , que es una forma elegante de decir que la membresía x ∈ A se puede decidir basándose solo en un número finito de elementos de $A$$\mathbb{N}^\mathbb{N}$$x \in A$$x$. Por ejemplo, el juego en el que la jugadora I gana si ella es la primera en jugar un número par está abierto. Otro ejemplo simple de juegos determinados son los juegos cerrados, es decir, juegos donde se puede decidir en base a una subsecuencia finita de x . Los juegos cerrados son juegos abiertos con los roles de los jugadores invertidos.$x \not \in A$$x$

Ahora podemos llegar a la determinación de Borel, y justo después intentaré vincular esto con los circuitos y la complejidad. Un conjunto Borel es un conjunto que puede derivarse de conjuntos abiertos y cerrados mediante la aplicación repetida de un número contable de uniones e intersecciones. Debe pensar en los conjuntos abiertos y cerrados como sus conjuntos básicos, y los conjuntos Borel como derivados de conjuntos básicos que utilizan varios niveles de un número "pequeño" (= contable) de operaciones simples en cada nivel. Resulta que puedes probar en ZFC que los conjuntos de Borel están determinados, y hay una sensación precisa de que esto es lo mejor que puedes hacer.

La analogía que creo que Gowers está dibujando aquí es que los conjuntos Borel son como pequeños circuitos. En el mundo finito, reemplazamos el "universo" por el hipercubo { 0 , 1 } n . Nuestros conjuntos básicos se convierten en facetas del cubo: { x ∈ { 0 , 1 } n : x i = b } para b ∈ { 0 , 1 } ; estos son equivalentes a literales x i y ˉ 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$. Puede escribir AND y OR de literales como uniones e intersecciones de dichos conjuntos. Entonces, para las funciones booleanas , poder producir f - 1 ( 1 ) a partir de s uniones e intersecciones de conjuntos básicos es equivalente a tener un circuito de tamaño s para f .$f:\{0,1\}^n \rightarrow \{0,1\}$$f^{-1}(1)$$s$$s$$f$

Permítanme lanzar una palabra sobre conjuntos analíticos. Un conjunto analítico es una proyección de un conjunto Borel: si es un conjunto Borel, entonces T = { x : ∃ y ( x , y ) ∈ S } es analítico. Por nuestra correspondencia entre los conjuntos Borel y las funciones de complejidad de circuito pequeño, los conjuntos analíticos son como NP / poly.$S \subseteq X \times Y$$T = \{x: \exists y\ (x,y) \in S\}$

Ahora se inspira en una prueba de la determinación de Borel para llegar a una propiedad (en el sentido de Razborov-Rudich) para distinguir funciones de complejidad de circuito pequeño de funciones de complejidad de circuito grande. La esperanza, por supuesto, es que la propiedad evite la barrera de las pruebas naturales.

La prueba de Martin de la determinación de Borel utiliza un enfoque conceptual muy ordenado: Martin muestra que cada juego de Borel es la imagen de un juego abierto (de hecho, clopen) bajo un mapa , de modo que $\pi$$\pi$preserva las estrategias ganadoras. Llamemos a esto un "levantamiento". Entonces, lo que Martin muestra es que cada juego de Borel es la imagen de un juego en el que el conjunto ganador es un conjunto básico. Dado que los juegos abiertos son fáciles de determinar, esto demuestra la determinación de Borel. La prueba es inductiva, con el caso base que muestra que los juegos cerrados se pueden levantar. La parte importante es que cada paso de la inducción "explota" el universo: deshacerse de un nivel de la construcción del conjunto Borel requiere elevar un juego a un juego sobre un universo que es esencialmente el conjunto de poder del universo del juego original . Curiosamente, esto es inevitable: los conjuntos de Borel que requieren más niveles para definirse solo pueden elevarse a juegos sobre universos mucho más grandes. Los conjuntos analíticos requieren universos que sean tan grandes que su existencia requiera grandes axiomas cardinales.

Inspirándose en esto, Gowers formula un juego en el que el jugador I y el jugador II deben especificar conjuntamente alguna ; el jugador I gana si f ( x ) = 1 , de lo contrario gana el jugador II. El jugador I puede especificar la primera mitad de las coordenadas, y el jugador II la segunda mitad. La intuición ahora es que los juegos correspondientes a f simple , es decir, f con complejidad de circuito pequeño, deberían permitir un ascenso al estilo Martin a un universo relativamente pequeño, al igual que los juegos de Borel. Por otro lado, la f aleatoria debería requerir universos de doble tamaño exponencial, y es de esperar que NP-hard f también debería, porque corresponderían a juegos analíticos.$x$$f(x) = 1$$f$$f$$f$$f$

Permítanme ser un poco más concreto sobre lo que es un ascensor de estilo Martin, pero revise las publicaciones de Gowers para obtener definiciones técnicas. Un levantamiento al estilo Martin (en la terminología de Gowers, "Ramsey") es un levantamiento a un juego de especificar alguna coordenada por coordenada, donde U es el universo y es potencialmente mayor que 2 n , pero ahora la condición ganadora es muy simple: si el jugador I o II gana se decide en función del valor de una sola coordenada de y . Como en la prueba de Martin, un ascensor debe preservar las estrategias ganadoras.$y \in U$$U$$2^n$$y$

$f$