Программа Малмули GCT

38

Иногда утверждают, что теория геометрической сложности Кетана Малмулей является единственной правдоподобной программой для решения открытых вопросов теории сложности, таких как вопрос P против NP. Было несколько положительных комментариев от известных теоретиков сложности о программе. По словам Малмулей, для достижения желаемых результатов потребуется много времени. Вход в область не прост для теоретиков общей сложности и требует значительных усилий, чтобы получить представление об алгебраической геометрии и теории представлений.

  1. Почему GCT считается способным противостоять P против NP? Какова стоимость заявки, если ожидается, что она займет более 100 лет? Каковы его преимущества перед другими нынешними подходами и теми, которые могут возрасти в ближайшие 100 лет?

  2. Каково текущее состояние программы?

  3. Какова следующая цель программы?

  4. Была ли какая-либо фундаментальная критика программы?

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

cc.complexity-theory big-picture algebraic-complexity p-vs-np gct анонимное
источник
12
Вы видели учебное пособие Малмулей на FOCS (доступно на techtalks.tv/talks/1301 ) и читали ли вы экспозицию Кена Ригана: theorie.informatik.uni-ulm.de/Personen/toran/beatcs/… ? Малмулей определенно дал понять, почему он считает, что его программа жизнеспособна (и я думаю, он утверждает, что это даже в какой-то степени необходимо), а также почему это сложно.
Сашо Николов
5
Похожие посты в блоге: 1 , 2 . Также Скотт пишет: «Программа Малктона GCT - единственный подход к P против NP, который я видел, у которого даже есть серьезное стремление« узнать о »множестве нетривиальных методов решения проблем в P (по крайней мере, сопоставление и линейное программирование) Для меня это, наверное, самый сильный аргумент в пользу GCT ".
Каве
7
Я думаю, что GCT нацелен на VP против VNP, а не на P против NP.
Иддо Цамерет
6
@Iddo: На самом деле он может быть нацелен на многие вещи (больше, чем на данный момент). Для "завивки об DET над " оно направлено на ¯ V P ш с VS V N P (см arxiv.org/abs/0907.2850 ). Однако для конечных полей и для функций, отличных от perm и det, он может быть нацелен непосредственно на P vs NP. СВпвесs¯ВNп
Джошуа Грохов
4
@ Мохаммед: То, что решение будет неожиданным и потребует совершенно новых идей, не означает, что это не так. В самом деле, многие уже полагают, что для разрешения P против NP любым методом потребуются совершенно новые идеи ...
Джошуа Грохов

Ответы:

23

Как отмечали многие другие, Малмулей, Риган и другие уже много говорили по многим из этих вопросов. Я предложу здесь только краткое изложение того, что я считаю некоторыми ключевыми моментами, которые еще не были упомянуты в комментариях.

  1. Относительно того, почему GCT считается правдоподобно способным показать многие ответы уже были даны в других местах и ​​в комментариях выше, хотя я думаю, что никто еще не упомянул, что кажется, что он избегает известных барьеров (релятивизация, алгебризация, естественные доказательства ). Что касается его ценности - я думаю, что даже если нам потребуется 100 лет, мы узнаем что-то новое о сложности на этом пути, изучая его с этой точки зрения.п≠Nп

    • Некоторый прогресс достигнут в понимании алгебраических многообразий, представлений и алгоритмических вопросов, возникающих в GCT. Из известных мне исследователей, которые работали над этим (в произвольном порядке): П. Бургиссер, К. Икенмейер, М. Кристандл, Дж. М. Ландсберг, К. В. Субрахманян, Дж. Блазяк, Л. Манивель, Н. Рессайре, Дж. Вейман, В. Попов, Н. Каял, С. Кумар и, конечно, К. Малмулей и М. Сохони.

    • N2+232N2+О(N)

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

  3. У меня нет ничего более конкретного, чтобы сказать по этому поводу, чем ответ на 2.

  4. Насколько я знаю, фундаментальной критики не было , в том смысле, что я не видел никакой критики, которая реально дискредитирует программу. Конечно, обсуждалась необходимость таких методов, ценность программы с учетом ожидаемых долгосрочных горизонтов и т. Д., Но я бы охарактеризовал их скорее как здоровую дискуссию, чем фундаментальную критику.

Джошуа Грохов
источник
1
@ user124864: в принципе да. GCT - это просто подход к отображению нижних границ, какими бы они ни были. Кажется, что это должно работать лучше для функций, характеризуемых их симметриями, но последнее свойство не зависит от числового значения нижней границы, которую вы хотите показать (например, квазиполя против exp).
Джошуа Грохов