Как геометрический подход Малмулей-Сохони к получению нижних оценок позволяет избежать естественных доказательств (в смысле Разборова-Рудича)?

Точная формулировка названия принадлежит Ананду Кулькарни (который предложил создать этот сайт). Этот вопрос был задан в качестве примера вопроса, но мне безумно любопытно. Я очень мало знаю об алгебраической геометрии, и на самом деле у меня есть только беглое понимание студентами препятствий, которые играют в вопросе P / poly против NP (нерелятивизирующий, неалгебразирующий, скорее всего, не будет естественным доказательством) ,

Что заставляет алгебраическую геометрию казаться, что она может обойти подобные препятствия? Это просто полевая экспертная интуиция или у нас есть действительно веские основания полагать, что этот подход фундаментально более эффективен, чем предыдущие? Каких более слабых результатов удалось достичь этому подходу?

[Я отвечу на вопрос, как указано в заголовке, оставив список других вопросов о GCT для других тем.] Для доказательства гипотез, возникающих в GCT, кажется, что он будет решающим образом использовать тот факт, что рассматриваемые функции (определяющие и постоянные, и другие связанные многочлены для P / poly и NP) характеризуются их симметриями. Эта необходимость является не формальным результатом, а интуицией, высказанной несколькими экспертами. (По сути, при отсутствии характеристики симметриями, понимание возникающей алгебраической геометрии и теории представлений гораздо сложнее.)

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

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

[В ответ на комментарий Росса Снайдера, вот объяснение характеристики симметриями.]

Сначала объяснение на примере. Для примера определите вспомогательную функцию . Если - матрица перестановок, то а если - диагональ, то (произведение диагональных элементов). Теперь предположим, что - однородный многочлен степени от переменных (который мы рассматриваем как входы матрицы ). Если имеет следующие симметрии:$q$q ( A ) = 1 A q ( A ) = d e t ( A ) p ( X ) n n 2 n × n X $A$$q(A)=1$$A$$q(A)=det(A)$$p(X)$$n$$n^2$$n \times n$$X$$p$

• $p(X) = p(X^t)$ (транспонировать)
• ( A , B ) A B q ( A ) q ( B ) = $p(AXB) = p(X)$ для всех пар матриц , так что каждая из и является либо матрицей перестановок, либо диагональными матрицами и$(A,B)$$A$$B$$q(A)q(B) = 1$

то является постоянным кратным для всех матриц . Следовательно, мы говорим, что перманент характеризуется своей симметрией.p e r m ( X ) $p(X)$$perm(X)$$X$

Вообще, если мы имеем (однородный) многочлен в переменных, то (группа всех обратимых матрицы) действует на по для (где мы берем переменные как основание для мерного векторного пространства, в котором естественным образом действует). Стабилизатором в является подгруппа . Мы говоримм Г л м м × м е ( е ) ( х 1 , . . . , х т ) = е ( - 1 ( х 1 ) , . . . , A - 1 ( x m ) ) A ∈ $f(x_1, ..., x_m)$$m$$GL_m$$m \times m$$f$$(Af)(x_1,...,x_m) = f(A^{-1}(x_1),...,A^{-1}(x_{m}))$х 1 , . , , , x m m G L m f G L m Stab ( f ) = { A ∈ G L m : A f = f } f f ′ m f A f ′ = f ′ A ∈ Stab ( f ) f ′$A \in GL_m$$x_1,...,x_m$$m$$GL_m$$f$$GL_m$$\text{Stab}(f) = \{ A \in GL_m : Af = f\}$$f$характеризуется его симметрий , если выполнено следующее: для любого однородного полинома в переменных одного и того же степени , как , если для всех , то есть постоянное кратное .$f'$$m$$f$$Af' = f'$$A \in \text{Stab}(f)$$f'$$f$

Ответ Джошуа Грохова хороший, но я думаю, что стоит сделать более общий комментарий. Результат Разборова – Рудича говорит о том, что если вы хотите доказать, что некоторая булева функция отсутствует в , то (предполагая, что вы верите их криптографической гипотезе), вы должны использовать некоторое свойство этой функции, которое либо нетривиально для вычисления, либо это разделяется только небольшим количеством других булевых функций. На практике нелегко придумать подходящие свойства; однако наблюдение Разборова – Рудича на самом деле не исключает очень многих общих планов нападения на нижние границы схемы при отсутствии конкретных подробностей о предполагаемом доказательстве. Например, предположим, я должен был наивно сказать, что мой план доказать$P/poly$$NP\not\subseteq P/poly$$SAT\notin P/poly$$SAT$$NP$$NP$

Иными словами, Разборов-Рудич обычно не представляет большого препятствия на ранних этапах планирования линии атаки на нижних границах цепи, если вы оставляете некоторое пространство в своем плане для использования в конечном итоге «специальных свойств». вашего кандидата булевых функций. Только когда вы закатываете рукава и пытаетесь заполнить детали аргумента, барьер натурализации начнет всерьез поднимать голову. Учитывая, что GCT все еще находится на ранней стадии разработки, мы не должны ожидать, что нам придется много беспокоиться о натурализации (хотя, конечно, стоит проверить, что программа GCT не обречена по тривиальным причинам).

Возможно, вы также захотите ознакомиться с изложением Кена Ригана о GCT, в котором есть некоторые замечания о барьере натурализации.