Подход Гауэрса к «дискретизированной борелевской определенности»

Гауэрс недавно изложил проблему, которую он называет «дискретизированной определенностью Бореля», решение которой связано с доказательством нижних границ схемы.

1. Можете ли вы дать краткое изложение подхода, ориентированного на аудиторию теоретиков сложности?

2. Что потребуется для этого подхода, чтобы доказать что-либо , включая повторное доказательство известных нижних границ?

Позвольте мне дать краткое изложение моего понимания мотивации для подхода. Имейте в виду, что я довольно плохо знаком с понятием определенности Бореля и совсем не являюсь экспертом в теории множеств. Все ошибки мои. Также я не уверен, что читать это намного лучше, чем читать посты Говерса.

Я думаю, что Гауэрс имеет в виду не конечный аналог теоремы Бореля об определенности, а конечный аналог следующего: определенность Бореля следует из ZFC, в то время как определенность аналитических игр требует существования (по существу) измеримых кардиналов. Я очень кратко опишу, о каких играх мы говорим и что такое определенность Бореля, и затем я свяжу это с подходом к доказательству нижних границ. Идея очень высокого уровня состоит в том, чтобы рассмотреть свойство «позволяет конечному аналогу доказательства определенности Бореля работать» как свойство, которое может отделить P \ poly от NP.

Мы думаем об играх, в которых два игрока I и II по очереди «играют» целое число. Игра продолжается вечно, поэтому они производят последовательность . Игра определяется выигрышным набором A ⊆ N N (т. Е. Набором последовательностей). Если x ∈ A, то выигрывает игрок I, в противном случае выигрывает игрок II.$x= x_1, x_2, \ldots$$A \subseteq \mathbb{N}^\mathbb{N}$$x \in A$

Игра определяется, если у игрока I или игрока II есть выигрышная стратегия: способ решить следующий ход, основанный на игре до сих пор, который гарантирует победу. То, все ли игры определены, оказывается, имеет тесную связь с основами теории множеств (это не так, если верить аксиоме выбора). В любом случае, один простой пример, когда игры фактически определены, это когда открыто в топологии продукта на N N , что является причудливым способом сказать, что членство x ∈ A может быть решено на основе только конечного числа элементов $A$$\mathbb{N}^\mathbb{N}$$x \in A$$x$, Например, игра, в которой игрок I выигрывает, если она первая играет четное число, открыта. Другой простой пример определенных игр - это закрытые игры, то есть игры, в которых может быть определено на основе конечной подпоследовательности x . Закрытые игры - это открытые игры с перевёрнутыми ролями игроков.$x \not \in A$$x$

Теперь мы можем прийти к определению Бореля, и сразу после этого я попытаюсь связать это со схемами и сложностью. Борелевское множество - это множество, которое может быть получено из открытых и закрытых множеств путем многократного применения счетного числа объединений и пересечений. Вы должны рассматривать открытые и закрытые множества как свои базовые множества, а борелевские множества как производные от базовых множеств, используя несколько уровней «небольшого» (= счетного) числа простых операций на каждом уровне. Оказывается, вы можете доказать в ZFC, что борелевские множества определены, и есть точный смысл, в котором это лучшее, что вы можете сделать.

Аналогия, которую, как мне кажется, Говерс проводит здесь, состоит в том, что борелевские множества подобны маленьким цепям. В конечном мире мы заменяем «вселенную» гиперкубом { 0 , 1 } n . Наши базовые множества становятся гранями куба: { x ∈ { 0 , 1 } n : x i = b } для b ∈ { 0 , 1 } ; они эквивалентны литералам x 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$, Вы можете написать И и ИЛИ литералов как объединения и пересечения таких множеств. Таким образом, для булевых функций возможность получения f - 1 ( 1 ) из s объединений и пересечений базовых множеств эквивалентна наличию схемы размера s для f ,$f:\{0,1\}^n \rightarrow \{0,1\}$$f^{-1}(1)$$s$$s$$f$

Позвольте мне добавить слово об аналитических множествах. Аналитическое множество является проекцией борелевского множества: если - борелевское множество, то T = { x : ∃ y ( x , y ) ∈ S } является аналитическим. По нашему соответствию между борелевскими множествами и функциями малой сложности схем, аналитические множества подобны NP / poly.$S \subseteq X \times Y$$T = \{x: \exists y\ (x,y) \in S\}$

Теперь он черпает вдохновение из доказательства определенности Бореля, чтобы придумать свойство (в смысле Разборова-Рудича) отличать функции малой сложности от функций большой сложности. Конечно, надежда состоит в том, что собственность избегает естественного барьера доказательств.

В доказательстве Мартина об определенности Бореля используется концептуально очень аккуратный подход: Мартин показывает, что каждая борелевская игра представляет собой изображение открытой (фактически закрытой) игры под картой , так что $\pi$$\pi$сохраняет выигрышные стратегии - давайте назовем это «лифт». Итак, Мартин показывает, что каждая борелевская игра - это образ игры, в которой выигрышный набор является базовым. Поскольку открытые игры легко увидеть, чтобы быть определенным, это доказывает определенность Бореля. Доказательство носит индуктивный характер, базовый случай показывает, что закрытые игры можно отменить. Важной частью является то, что каждый шаг индукции «взрывает» вселенную: избавление от одного уровня конструкции набора Бореля требует превращения игры в игру над вселенной, которая по сути является набором мощности вселенной исходной игры. , Интересно, что это неизбежно: наборы Бореля, для определения которых требуется большее количество уровней, могут быть применены только к играм в гораздо больших вселенных. Аналитические множества требуют, чтобы юниверсы были настолько велики, что их существование требует больших кардинальных аксиом.

Черпая вдохновение в этом, Гауэрс формулирует игру, в которой игрок I и игрок II должны совместно указать несколько ; игрок I выигрывает, если f ( x ) = 1 , иначе игрок II выигрывает. Игроку я могу указать первую половину координат, а игроку II - вторую половину. Интуиция теперь заключается в том, что игры, соответствующие простому f , то есть f с малой сложностью контуров, должны позволять мартинскому стилю подниматься в относительно небольшую вселенную, как это делают борелевские игры. С другой стороны, случайное f должно требовать двойных экспоненциальных юниверсов, и, надеемся, NP-hard f также должно быть, потому что они соответствуют аналитическим играм.$x$$f(x) = 1$$f$$f$$f$$f$

$y \in U$$U$$2^n$$y$

$f$