Объяснение теории геометрической сложности в стиле Википедии

Может ли кто-нибудь дать краткое объяснение подхода Малмулей к GCT, понятное неспециалистам? Объяснение, которое подойдет для страницы Википедии по этой теме (которая на данный момент является заглушкой).

Мотивация: я «читаю» книгу Скотта Ааронсона «Квантовые вычисления» со времен Демокрита с моим другом, который является исследователем в теории струн. В предисловии к книге Ааронсон называет GCT «струнной теорией информатики». Будучи теоретиком струн, мой друг был взволнован этим утверждением и спросил меня, что такое GCT. В тот момент я позорно осознал, что у меня нет готового к Википедии ответа на его вопрос.

Я не совсем уверен, какой уровень подходит для статьи в Википедии (разные статьи нацелены на разные уровни знаний) или именно то, что вы ищете. Итак, вот попытка, но я открыт для обратной связи.

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

Как и во многих предыдущих подходах, конечная цель состоит в том, чтобы отделить два класса сложности , показав, что существует полином который принимает функции качестве входных данных (скажем, в силу их векторов коэффициентов) таких, что обращается в нуль на каждой функции но не обращается в нуль на некоторой функции . pfpf∈ C e a s y g h a r d ∈ C h a r $\mathcal{C}_{easy}, \mathcal{C}_{hard}$$p$$f$$p$$f \in \mathcal{C}_{easy}$$g_{hard} \in \mathcal{C}_{hard}$

Первая ключевая идея (см. [GCT1, GCT2]) состоит в том, чтобы использовать симметрии для организации не самих функций, а для организации ( алгебро-геометрических ) свойств этих функций, которые фиксируются полиномами, такими как выше. Это позволяет использовать теорию представлений при попытке найти такой . Подобные идеи, относящиеся к теории представлений и алгебраической геометрии, использовались в алгебраической геометрии и раньше, но, насколько мне известно, никогда не были такими.$p$$p$

Вторая ключевая идея (см. [GCT6]) состоит в том, чтобы найти комбинаторные (и полиномиальные) алгоритмы для результирующих теоретико-представительных задач, а затем перепроектировать эти алгоритмы, чтобы показать, что такой существует. Это может быть принято в духе использования линейного программирования (алгоритма) для доказательства некоторых чисто комбинаторных утверждений.$p$

В самом деле, [GCT6] предлагает свести теоретико-представительные проблемы, описанные выше, к задачам целочисленного программирования , затем показать, что полученные IP-адреса решаются путем их релаксации LP, и, наконец, дать комбинаторные алгоритмы для полученных LP. Гипотезы в [GCT6] сами по себе мотивированы обратным инжинирингом известных результатов для коэффициентов Литтлвуда-Ричардсона, аналогичной, но более простой проблемы в теории представлений. В случае коэффициентов LR комбинаторное правило Литтлвуда-Ричардсона пришло первым. Позже Беренштейн и Зелевинский [BZ] и Кнутсон и Тао [KT] (см. [KT2] для дружественного обзора) дали IP для коэффициентов LR. Кнутсон и Тао также доказали гипотезу насыщения, из которой следует, что IP решается с помощью релаксации ЛП (см. [GCT3, BI]).

Результаты [GCT5] показывают, что явная дерандомизация леммы Нётера о нормализации по существу эквивалентна пресловутой открытой задаче в теории сложности дерандомизации черного ящика при тестировании полиномиальной идентичности . Грубо говоря, как это вписывается в большую программу, так это нахождение явного базиса для функций которые (не) исчезают на (в этом случае класс, для которого определитель полон), может быть используется для выведения комбинаторного правила для искомой задачи в теории представлений, как это происходило в других ситуациях в алгебраической геометрии. Промежуточным шагом здесь было бы найти основу для тех которые (не) исчезают при нормализацииС й ы у р С й ы $p$$\mathcal{C}_{easy}$$p$$\mathcal{C}_{easy}$ , который по построению является более хорошим алгебраическим многообразием - другими словами, чтобы дерандомизировать нормировочную лемму Нётера для DET.

Примеры симметрий сложности и функций

Например, сложность функции - для большинства естественных понятий сложности - остается неизменной, если мы переставляем переменные некоторой перестановкой . Таким образом, перестановки являются симметриями самой сложности. Для некоторых понятий сложности (таких как сложность алгебраических схем) все обратимые линейные изменения переменных являются симметриями.f ( x π ( 1 ) , … , x π ( n ) ) $f(x_1, \dotsc, x_n)$$f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$$\pi$

Отдельные функции могут иметь дополнительные симметрии. Например, определитель имеет симметрии для всех матриц таких что . (Из того, что я мало понял об этом, я понимаю, что это аналогично явлению самопроизвольного нарушения симметрии в физике.)det ( A X B ) = det ( X T ) = det ( X ) A , B det ( A B ) = $\det(X)$$\det(AXB) = \det(X^{T}) = \det(X)$$A,B$$\det(AB) = 1$

Некоторый недавний прогресс [этот раздел определенно неполный и более технический, но полный отчет занял бы десятки страниц… Я просто хотел бы выделить некоторый недавний прогресс]

Бургиссер и Икенмейер [BI2] показали нижнюю границу для умножения матриц после программы GCT, поскольку в ней используются представления с нулевыми и ненулевыми кратностями. Ландсберг и Оттавиани [LO] дали наиболее известную нижнюю границу, по существу, граничного ранга умножения матриц, используя теорию представлений для организации алгебраических свойств, но не используя кратности представлений и комбинаторные правила.2n$\frac{3}{2}n^2$$2n^2$

Следующая проблема после коэффициентов Литтлвуда-Ричардсона - это коэффициенты Кронекера . Они проявляются как в ряде проблем, которые, как предполагается, в конечном итоге достигают теоретико-представительных проблем, возникающих в GCT, так и непосредственно в виде границ множественности в подходе GCT к умножению матриц и постоянным по сравнению с детерминантом. Нахождение комбинаторного правила для коэффициентов Кронекера является давней открытой проблемой в теории представлений; Blasiak [B] недавно дал такое комбинаторное правило для коэффициентов Кронекера с одной формой крючка.

Кумар [K] показал, что некоторые представления появляются в координатном кольце определителя с ненулевой кратностью, предполагая гипотезу латинского квадрата столбца (см. Хуанг-Рота и Алон-Тарси; эта гипотеза также, возможно, не случайно, обнаруживается в [BI2 ]). Следовательно, эти представления не могут использоваться для отделения перманента от определителя на основе нулевых и ненулевых кратностей, хотя все еще возможно использовать их для отделения перманента от определителя с помощью более общего неравенства между кратностями.

Список литературы [B] J. Blasiak. Коэффициенты Кронекера для одной формы крючка. arXiv: 1209.2018, 2012.

[Б.И.] П. Бургиссер и К. Икенмейер. Алгоритм максимального потока для положительности коэффициентов Литтлвуда-Ричардсона. FPSAC 2009.

[BI2] П. Бургиссер и К. Икенмейер. Явные нижние оценки с помощью теории геометрической сложности. arXiv: 1210.8368, 2012.

[BZ] А.Д. Беренштейн и А.В. Зелевинский. Тройные кратности для и спектр внешней алгебры присоединенного представления. $\mathfrak{sl}(r+1)$Дж. Алгебраический Комбин. 1 (1992), нет. 1, 7–22.

[GCT1] К.Д. Малмулей и М. Сохони. Теория геометрической сложности I: подход к P против NP и смежным проблемам. SIAM J. Comput. 31 (2), 496–526, 2001.

[GCT2] К.Д. Малмулей и М. Сохони. Теория геометрической сложности II: На пути к явным препятствиям для вложений среди многообразий классов. SIAM J. Comput., 38 (3), 1175–1206, 2008.

[GCT3] К.Д. Малмулей, Х. Нараянан и М. Сохони. Геометрическая теория сложности III: о решении неисчезания коэффициента Литтлвуда-Ричардсона. Дж. Алгебраический Комбин. 36 (2012), нет. 1, 103–110.

[GCT5] К.Д. Малмулей. Теория геометрической сложности V: Эквивалентность между дерандомизацией черного ящика проверки полиномиальной идентичности и дерандомизацией леммы Нётера о нормализации FOCS 2012, также arXiv: 1209.5993.

[GCT6] К.Д. Малмулей. Теория геометрической сложности VI: переворот через позитивность. , Технический отчет, факультет компьютерных наук, Чикагский университет, январь 2011 г.

[K] С. Кумар. Исследование представлений, поддерживаемых замыканием орбиты определителя. arXiv: 1109.5996, 2011.

[LO] Дж. М. Ландсберг и Г. Оттавиани. Новые нижние оценки для ранга границы умножения матриц. arXiv: 1112.6007, 2011.

[KT] А. Кнутсон и Т. Тао. Сотовая модель тензорных произведений . I. Доказательство гипотезы насыщения. $\text{GL}_n(\mathbb{C})$J. Amer. Математика Soc. 12 (1999), № 4, 1055–1090.

[KT2] А. Кнутсон и Т. Тао. Соты и суммы эрмитовых матриц. Заметки амер. Математика Soc. 48 (2001), нет. 2, 175–186.

Недавно я дал ответ на связанный вопрос о Mathoverflow https://mathoverflow.net/questions/277408/what-are-the-current-breakthroughs-of-geometric-complexity-theory

Поскольку этот сайт, возможно, является лучшим местом, позвольте мне повторить этот ответ ниже. Ссылки на Джозефа или Тимофея о других постах по этому вопросу МО.

---

Пусть - общая матрица а - однородный многочлен степени определяемый как определитель. Пусть который принимает постоянная подматрицы и умножается на любимую линейную форму, чтобы сделать другой однородный многочлен степени (можно также использовать запись вместо ). Эта модификация называется дополнением . Затем определите число n × n F 1 ( X ) = d e t ( X ) n F 2 ( X ) = ( X n n ) n - m × p e r m [ ( X i j ) 1 ≤ i , j $X=(X_{ij})_{1\le i,j\le n}$$n\times n$$F_1(X)={\rm det}(X)$$n$

$$F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right]$$ $m\times m$$n$$X_{11}$$X_{nn}$ $$c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \}$$ где в , действующий на аффинном пространстве размерности , где живет и Зарискому замыкания орбит. Большая гипотеза в этой области или гипотеза Валианта (сложная версия ) состоит в том, что растет быстрее, чем любой многочлен от .$G$$GL(n^2)$$n^2$$X$$\overline{G\cdot F_i}$${\rm P}\neq{\rm NP}$$c(m)$$m$

Теперь, если , то имеется сюръективное -эквивариантное отображение между частями степени колец координат этих замыканий орбиты. Таким образом, игра состоит в том, чтобы попытаться показать, что этого не происходит для недостаточно большого по отношению к , путем доказательства существования препятствия множественности , т.е. неприводимого представления для которого кратности удовлетворяют $\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$$G$

$$\mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d$$ $d$$n$$m$$\lambda$ $${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)$$ или на уровне идеалов $${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ .$$

Оптимистический подход состоит в том, чтобы попытаться показать, что существуют препятствия вхождения , т. такие, что и . Эта надежда была разрушена в работе Bürgisser, Ikenmeyer и Panova, упомянутой Тимоти. Однако, возможность препятствий множественности все еще открыта.$\lambda$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$

Я думаю, что подход Малмулей состоит в том, чтобы попытаться доказать существование таких препятствий множественности, используя все инструменты, доступные в теории представлений для вычисления этих кратностей. Лично я никогда не был поклонником такого подхода. Изучив теорию инвариантов 19-го века в некоторой глубине, мне кажется более естественным подходить к проблеме разделения орбит с использованием явных инструментов той эпохи. Эта статья Горхова, кажется, также указывает на аналогичное направление (я подозреваю, что третья статья, упомянутая Джозефом, находится в том же духе). В классическом языке (см. Тернбулл или Литтлвуд ) нужно явно создать смешанный сопутствующий который исчезает на$F_1$но не на . Нужно также делать это бесконечно часто (в ), чтобы установить свойство суперполиномиального роста. Такой сопутствующий компонент аналогичен конкретному -эквивариантному отображению из вашей любимой модели неприводимого представления в полиномиальную алгебру в переменных (Грохов называет это разделяющим модулем ). Инвариантные теоретики 19-го века имели два метода для генерации таких объектов: теория исключения и диаграммная алгебра .$F_2$$m$$G$$\lambda$$n^2$$X$

Очень маленький пример, где и - это двоичные квартичные формы под действием (см. Этот вопрос МО ): и Разделяющий сопутствующий (здесь на самом деле ковариантный) - это гессиан общей двоичной квартики Он исчезает (тождественно по ) для но не для$F_1$$F_2$$G=SL(2)$

$$F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4$$ $$F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ .$$ $F$ $$H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ .$$ $x,y$$F=F_1$$F=F_2$, В этом случае гессиан можно рассматривать как эквивариантное отображение из неприводимости, заданной второй симметричной степенью (фундаментального двумерного представления), в координатное кольцо для аффинного пространства бинарных квартик.

Таким образом, возможный супероптимистический «план» для GCT включает следующую последовательность шагов.

1) Найти способ генерировать тонны сопутствующих факторов.

2) Определите несколько явных кандидатов на исчезновение на и докажите это свойство.$F_1$

3) Показать, что они не исчезают на .$F_2$

Шаг 1) в принципе решается Первой фундаментальной теоремой для но существует несоответствие: определитель является естественным объектом в теории инвариантов для (действует на строки и столбцы), а не . Можно попытаться исправить несоответствие, выразив основной строительный блок для теории инвариантов через единицу для (см. Этот вопрос MO для аналогичной задачи редукции). от до ).$GL(n^2)$$GL(n)\times GL(n)$$GL(n^2)$$GL(n^2)$$GL(n)\times GL(n)$$SL(n(n+1)/2)$$SL(n)$

Угадай правильных кандидатов на Шаг 2), мне тяжело. Зная заранее, что некоторые кратности от нуля, определенно помогло бы. Хотя, можно отложить и отложить доказательство неидентичного исчезновения сопутствующего шага 3), которое в любом случае должно показать больше, чем это. Если у кого-то есть такие правильные кандидаты, показать, что они исчезают на можно легко с помощью аргументов, которые можно назвать принципом исключения Паули (сжатие симметризаций с антисимметризацией), свойством высокого хроматического числа или просто «недостатком места». F ${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$$F_1$

Тем не менее, я думаю, что самая сложная часть - это шаг 3). Например, в моей статье «16 051 формула для инварианта Оттавиани кубической тройки » с Икенмейером и Ройлом, угадывание было сделано с помощью компьютерного поиска, но с подходящим кандидатом в руку, исчезновение на было относительно легко объяснить (это довольно симпатичный пример хроматического числа из-за глобальных свойств графа, а не какой-то большой клики). Аналог шага 3) в нашей статье был сделан с помощью компьютерного расчета методом грубой силы, и мы до сих пор не знаем, почему это так. Парадигматическая проблема, связанная с Шагом 3) - это гипотеза Алон-Тарси (см. Этот вопрос МО и этот$F_1$слишком). По моему мнению, нужно продвинуться в решении этого вопроса ( теорема о четырех цветах также относится к этому типу посредством сокращения из-за Кауфмана и Бар-Натана) до гипотезы Валианта.

Поскольку речь идет о прорывах в GCT. Я думаю, что эта статья Ландсберга и Рессейра также заслуживает некоторого внимания, поскольку она предполагает, что разумное предположение для точного значения : Отметим, что доказательство концепции для явного подхода «Шаг 1), 2), 3)», в гораздо более простой задаче, было дано Bürgisser и Ikenmeyer в этой статье . Наконец, для получения дополнительной информации о GCT я настоятельно рекомендую обзор «Геометрическая теория сложности: введение в геометры» Ландсберга.( 2 м м ) - 1 $c(m)$

$$\left(\begin{array}{c}2m\\ m \end{array}\right)-1\ .$$

PS: я должен добавить, что мой пессимизм специфичен для Гипотезы Valiant, которая является «Гипотезой Римана» в этой области. Конечно, не следует бросать ребенка в ванну с водой и клеветать на ГКТ, потому что до сих пор не удалось доказать эту гипотезу. Есть много более доступных проблем в этой области, где достигнут прогресс и ожидается больший прогресс. См., В частности, вышеупомянутую статью Grochow и обзор Landsberg.

GCT - это исследовательская программа для доказательства границ теории сложности, которая в некоторой степени не поддается аннотации / резюме в стиле википедии из-за своей тяжелой абстракции, но для толпы TCS доступны хорошие обзоры. [2] [3] [4] (и, конечно, Википедия - лучшее место для записей в Википедии). он был сформулирован в начале 2000-х годов Малмулей и является относительно новым в теории сложности и очень продвинутым, используя и применяя продвинутую математику (алгебраическую геометрию), которая не возникла в TCS / теории сложности.

этот подход считается многообещающим для некоторых, но, возможно, слишком сложным для других органов, т. е. он не доказан и, следовательно, является спорным, может ли он преодолеть стандартные известные «барьеры». (в этом смысле он действительно демонстрирует некоторые признаки так называемого «сдвига парадигмы» Куна). Даже Малмулей предполагает, что он реально может не преуспеть (в доказательстве разделения классов большой сложности) после десятилетий дальнейшего развития. Вот скептическое мнение Fortnow, ведущего авторитета в области теории сложности: [1]

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

[1] Как доказать, что NP отличается от блога P Fortnow

[2] Понимание подхода Малмулей-Согони к P против NP Regan

[3] О P против NP и теории геометрической сложности Малмулей

[4] Программа GCT для решения проблемы P и NP Малмулей