Конструктивность в естественном доказательстве и геометрической сложности

Недавно Райан Уилламс доказал, что конструктивность в естественном доказательстве неизбежно приводит к разделению классов сложности: и . $\mathsf{NEXP}$$\mathsf{TC}^{0}$

Конструктивность в естественном доказательстве - это условие, которому удовлетворяют все комбинаторные доказательства в сложности схем и что мы можем решить, обладает ли целевая функция в $\mathsf{NEXP}$ (или других «сложных» классах сложности) «жестким» свойством с помощью алгоритма, который выполняется в poly-time в длине таблицы истинности целевой функции.

Два других условия: бесполезное условие, которое требует «жесткого» свойства, не может быть вычислено никакими схемами в $\mathsf{TC}^0$ и условие большого размера, которое трудно найти.

Мой вопрос:

Означает ли это, что геометрическая теория сложности (GCT) недоступна для решения основных проблем разделения, таких как vs , vs или vs ?$\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NC}$$\mathsf{NEXP}$$\mathsf{TC}^0$

Ссылки:

• Райан Уильямс, " Естественные доказательства против дерандомизации "

Нет, неизбежность конструктивности определенно все еще оставляет GCT открытым в качестве жизнеспособного плана атаки на проблемы с нижними границами, такие как против P / p o l y .$NP$$P/poly$

Во-первых, стоит упомянуть, что результат Райана о конструктивности очень похож на так называемый «теоремы Флип» Малмулей, который говорит, например, что если перманент не имеет многоразмерных арифметических схем, то есть рандомизированное множество раз за многократное время (полиномиально много) матриц такое, что каждая малая цепь отличается от перманента на одной из этих матриц. См. Явные доказательства и Флип, Технический отчет, Департамент компьютерных наук, Университет Чикаго, сентябрь 2010 г., Малмулей.$\{M_1, \dotsc, M_{p(n)}\}$

Во-вторых, центральная характеристика симметрии (упомянутая Сиуманом) в GCT стала более очевидной после опроса Риган. Если характеристика симметрии оказывается столь же важной для GCT, как кажется, она собирается это сделать, то это уже обходит условие крупности. Для определения характеристики симметрии, см. Этот ответ на тесно связанный предыдущий вопрос .

Доказательство того, что характеристика симметрии нарушает размерность, см. В разделе 3.4.3 «Характеристика симметрии избегает барьера Разборова-Рудича» в моей диссертации (бесстыдные самозаключения, но я не знаю где-нибудь еще, где это написано так полно) , Я подозреваю, что это также нарушает конструктивность, но оставил этот вопрос открытым. (Ранее в главе 3 также был представлен обзор теорем о перевороте в GCT и их связи с характеристикой симметрии.)

(Мне кажется интересным, что характеристика симметрии - то самое свойство, которое, как мы подозреваем, будет использовано в GCT, которое используется для Разборова - Рудича, - используется для доказательства теоремы переворота, которые по существу говорят, что конструктивность необходима.)

Наконец, стоит упомянуть, что, хотя в долгосрочной перспективе GCT нацелен на решение проблемы сравнению с P / p o l y и другими булевыми проблемами, в настоящее время большая часть работы в GCT сосредоточена на их алгебраических аналогах, таких как комплексные чисел, и пока нет алгебраического аналога Разборова - Рудича (о котором я знаю).$NP$$P/poly$

Позвольте мне сначала исправить возможное недоразумение: к сожалению, мы еще не знаем, что . Моя самая последняя нижняя граница Н Е Х Р ∩ C О Н Е Х Р ⊄ С С .$NEXP \not\subset TC^0$$NEXP \cap coNEXP \not\subset ACC$

Теперь ответ на ваш вопрос - нет. Это по - прежнему очень возможно , что методы , основанные на GCT можно отделить от N P .$P$$NP$

Еще несколько комментариев по этому поводу: связь между GCT и Natural Proofs обсуждалась в прошлом (даже в самих оригинальных статьях GCT). Несмотря на то, что, похоже, не было единодушного мнения о том, какая из «конструктивности» или «масштабности» будет нарушена подходом GCT, Малмулей и Сохони однажды утверждали, что, если GCT может быть проведен, тогда он должен нарушать масштабность. Для соответствующей ссылки см. Раздел 6 обзора Риган о GCT . Тем не менее, я должен добавить, что этому обзору уже 10 лет, и с тех пор в GCT проделана значительная работа; Я не уверен, есть ли пересмотренное / новое мнение по этому поводу. (Возможно, Джош Грохоу может вмешаться?)

Краткий ответ - нет .

Подход теории геометрической сложности нацелен на некое крайне редкое свойство, которое, как утверждает Малмулей, не является «большим», как это определено Разборовым и Рудичем. Формальный аргумент см. Также в тезисе Джошуа Грохова , раздел 3.4.3. Симметричная характеристика позволяет избежать барьера Разборова – Рудича , и его ответе .

Следующий абзац взят из книги « О P против NP и теории геометрической сложности» Кетана Малмулей ( JACM 2011 или рукопись ), раздел 4.3 «План высокого уровня» :

Цель состоит в том, чтобы выполнить эти шаги явно, используя характеристику симметриями перманента и определителя. Мы уточним, что означает явное позже; ср Гипотеза 4.6. Этот подход чрезвычайно жесткий в том смысле, что он работает только для чрезвычайно редких жестких функций, которые характеризуются их симметриями. Эта крайняя жесткость намного больше, чем требуется для обхода естественного барьера защиты [Разборов и Рудич 1997].

Поскольку для естественного доказательства требуются как условия конструктивности, так и масштабности (когда полезность подразумевается), доказательство того, что конструктивность неизбежна, недостаточно для исключения таких подходов (хотя это большой шаг вперед).