Несколько лет назад Джоэл Фридман сделал несколько работ, касающихся нижних границ цепей для когомологий Гротендика (см. Документы: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024. ). Принесло ли это направление мысли новое понимание булевой сложности, или это скорее математическое любопытство?
cc.complexity-theory
lower-bounds
circuit-complexity
boolean-functions
Марчин Котовски
источник
источник
Ответы:
Я переписывался с Джоэлом Фридманом около 3 лет назад на эту тему. В то время он сказал, что его подход не привел к каким-либо существенным новым взглядам на теорию сложности, хотя он все еще думал, что это многообещающая тактика.
По сути, Фридман пытается перефразировать проблемы сложности схем на языке пучков в топологии Гротендика. Есть надежда, что этот процесс позволит применить геометрическую интуицию к проблеме нахождения нижних границ схемы. Хотя, безусловно, стоит проверить, ведет ли этот путь куда-либо, существуют эвристические причины для скептицизма. Геометрическая интуиция работает лучше всего в контексте гладких многообразий или вещей, которые достаточно похожи на гладкие многообразия, чтобы интуиция не полностью разрушалась. Другими словами, вам нужна некоторая структура, чтобы геометрическая интуиция закрепилась. Но нижние границы схемы по самой своей природе должны противостоять произвольным вычислениямкоторые трудно анализировать именно потому, что они кажутся такими бесструктурными. Фридман сразу признает, что топологии Гротендика, которые он рассматривает, в высшей степени комбинаторны и далеки от обычных объектов исследования в алгебраической геометрии.
В качестве дополнительного комментария я бы сказал, что важно не слишком увлекаться идеей только потому, что она использует незнакомую, мощную технику. Механизм мог бы быть очень эффективным для решения проблем, для которых он был разработан, но для того, чтобы он был полезен для атаки на известную трудную проблему в другой области, должен быть какой-то убедительный аргумент, почему иностранный механизм хорошо приспособлен для решения фундаментальных задач. препятствие в проблеме интересов.
источник
Я думаю, что у Тимоти Чоу все в порядке. У меня есть свой личный список идей, включающих «гладкие» разновидности, или концепции, такие как подсчет соединенных компонентов или мономов, которые идут с несколькими нижними ступенями «лестницы когомологий» - все они показаны не как предикаты твердости (( варианты) конструкции Майра-Мейера, показывающей EXPSPACE-полноту различных проблем, связанных с GCT. Мой один рифф на своем последнем пункте, что я думаю , что некоторые рода мощных машин необходимо ...!
источник