Когомологический подход к булевой сложности

33

Несколько лет назад Джоэл Фридман сделал несколько работ, касающихся нижних границ цепей для когомологий Гротендика (см. Документы: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024. ). Принесло ли это направление мысли новое понимание булевой сложности, или это скорее математическое любопытство?

Марчин Котовски
источник
4
Мне очень любопытно увидеть ответ на это. Конечно, проще всего было бы написать Джоэлу Фридману по электронной почте :)
Suresh Venkat

Ответы:

28

Я переписывался с Джоэлом Фридманом около 3 лет назад на эту тему. В то время он сказал, что его подход не привел к каким-либо существенным новым взглядам на теорию сложности, хотя он все еще думал, что это многообещающая тактика.

По сути, Фридман пытается перефразировать проблемы сложности схем на языке пучков в топологии Гротендика. Есть надежда, что этот процесс позволит применить геометрическую интуицию к проблеме нахождения нижних границ схемы. Хотя, безусловно, стоит проверить, ведет ли этот путь куда-либо, существуют эвристические причины для скептицизма. Геометрическая интуиция работает лучше всего в контексте гладких многообразий или вещей, которые достаточно похожи на гладкие многообразия, чтобы интуиция не полностью разрушалась. Другими словами, вам нужна некоторая структура, чтобы геометрическая интуиция закрепилась. Но нижние границы схемы по самой своей природе должны противостоять произвольным вычислениямкоторые трудно анализировать именно потому, что они кажутся такими бесструктурными. Фридман сразу признает, что топологии Гротендика, которые он рассматривает, в высшей степени комбинаторны и далеки от обычных объектов исследования в алгебраической геометрии.

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

Тимоти Чоу
источник
4
Конечно, усилия Малмули идут по «схожим» линиям в смысле использования «гладких структур», но он рассматривает проблемы, которые допускают красивые геометрические инварианты для начала.
Суреш Венкат
2
@Suresh: Вы правы в том, что подход Малмулей-Сохони отличается, но фундаментальная проблема справиться с произвольным вычислением все еще скрывается на заднем плане, поэтому справедливо спросить, как можно рассчитывать на это. На данный момент я не думаю, что кто-то действительно знает, поэтому люди из GCT не обещают впечатляющих открытий в ближайшее время.
Тимоти Чоу
верно. Интересно увидеть документ STOC 2011, в котором для оценки умножения матриц используется GCT (и Кетан упомянул этот результат в своем уроке на FOCS)
Суреш Венкат,
1
@Suresh: Если вы говорите о статье Buergisser / Ikenmeyer, я думаю, что она говорит гораздо больше об ограничениях подхода GCT, чем о том, как доказать нижние оценки.
5501
1
@ Нет, у меня нет ответа, но мне интересно, заслуживает ли это своего собственного вопроса.
Суреш Венкат
16

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

Кеннет В. Риган
источник