Продвинутые методы определения сложности нижних границ

Некоторые из вас, возможно, следили за этим вопросом , который был закрыт из-за отсутствия уровня исследования. Итак, я извлекаю часть вопроса, которая находится на исследовательском уровне.

Помимо «более простых» техник, таких как приведение к сортировке или задача, полная по EXPTIME, какие методы были использованы для доказательства нижних границ сложности задачи во времени?

Особенно:

• Какие «передовые» методы были разработаны в последнее десятилетие?
• Можно ли применять методы из абстрактной алгебры, теории категорий или других разделов типично «чистой» математики? (Например, я часто слышу упоминание об «алгебраической структуре» сортировки без какого-либо реального объяснения того, что это значит.)
• Каковы значимые, но менее известные результаты для нижней оценки сложности?

Нижние оценки для алгебраических схем

В настройке алгебраических схем, где нижняя граница размера схемы аналогична нижней границе времени, известно много результатов, но в более современных результатах есть только несколько основных методов. Я знаю, что вы спрашивали о нижних границах времени, но я думаю, что во многих случаях надежда состоит в том, что алгебраические нижние оценки однажды приведут к нижним границам булевой / тьюринговской машин. Эти результаты часто используют более глубокие методы из "чистой математики", как вы выразились.

I. Степень привязки.

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

II. Связанные компоненты (или, в более общем случае, размерность любой группы с более высокой гомологией).

Бен-Ор показал, что размер реального алгебраического дерева решений, определяющего принадлежность к (полуалгебраическому) множеству, по крайней мере, где C - число связанных компонентов этого множества. Бен-Ор использовал это, чтобы доказать нижнюю границу Ω ( n log n ) для сортировки (ну, различие элементов, но различие элементов сводится к сортировке) в реальной алгебраической модели дерева решений. Яо расширил это от связанных компонент к сумме чисел Бетти и доказал оптимальные нижние оценки для других задач (таких как k- уравнения). В другой статье Яо распространил это на алгебраические деревья решений над целыми числами.$\log C$$C$$\Omega(n \log n)$$k$

III. Частные производные.

Это была рабочая лошадка многих нижних границ современной алгебраической схемы. Я полагаю, что частные производные были впервые использованы для доказательства нижней границы по Бауру-Штрассену, где они показали, что вычисление всех первых частей может быть выполнено в размере 5 с, где s - размер, необходимый для вычисления f . В сочетании с оценкой степени Штрассена это дало нижние границы размера Ω ( n log n ) для различных функций, которые по-прежнему являются самыми сильными нижними границами для размера неограниченных арифметических схем для явной функции.$f$$5s$$s$$f$$\Omega(n \log n)$

Более недавнее использование частных производных, по-видимому, вытекает из статьи Нисана, в которой он доказал нижние оценки некоммутативных цепей, рассматривая размерность пространства всех частных производных. Это было использовано Нисаном-Вигдерсоном для доказательства нижних границ для ограниченных типов схем глубины 3, и аналогичные идеи использовались для доказательства нижних границ для размера мультилинейной формулы Raz (и связанных моделей Raz и соавторов). Самые последние нижние границы глубины 4 и глубины 3 Гупты, Каяла, Камата и Саптариши используют обобщение этой идеи, чтобы подсчитать размерность пространства «сдвинутых частных производных» - где вы можете взять частные производные и затем умножить на любые мономы заданной степени. ) может «просто» быть вопросом лучшего понимания идеала, порожденного перманентными несовершеннолетними (см. Гипотезу в конце их статьи).$\mathrm{VP} \neq \mathrm{VNP}$

Внутривенно Определение уравнений для сортов.

Идея состоит в том, чтобы связать с «легкими функциями» определенное алгебраическое многообразие, найти уравнения, которые обращаются в нуль на этом многообразии, и показать, что эти уравнения не обращаются в нуль на вашей «жесткой функции». (Следовательно, доказательство того, что ваша сложная функция не входит в число простых функций, так что это действительно сложно.) Особенно полезно в нижних границах умножения матриц. См. Landsberg - Ottaviani на arXiv для последних и ссылки на предыдущие нижние границы.

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

V. Теория представлений, особенно как в теории геометрической сложности.

На самом деле, также используется Ландсберг - Оттавиани, чтобы найти некоторые уравнения для определенного разнообразия. Также используется Бургиссером-Икенмейером для получения «чисто» теоретико-представительного доказательства чуть более слабой нижней границы умножения матриц. Предполагается, что Малмулей и Сохони (см. «Теория геометрической сложности I и II») могут быть полезны для разрешения против V N P и, в конечном итоге, N P против P / p o l y .$\mathrm{VP}$$\mathrm{VNP}$$\mathrm{NP}$$\mathrm{P/poly}$

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

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

Я должен сказать, что многие аргументы 70-х и 80-х годов также можно сказать, что они следуют приведенной выше схеме; Основное отличие в настоящее время заключается в «других ингредиентах» - есть много ингредиентов на выбор, и способы их применения ограничены только вашим собственным творческим потенциалом. Иногда, когда вы не знаете, как смешивать определенные ингредиенты, чтобы получить лучший рецепт, но очень хорошо понимаете, как они могут смешиваться, это помогает кодировать компьютерную программу, которая предлагает вам новые рецепты.

Было бы очень интересно получить новые доказательства последних нижних оценок, которые окончательно не следуют этой парадигме. Например, может ли быть доказано без какой-либо ссылки на аргумент диагонализации? Начнем с того, можно ли это доказать, не прибегая к недетерминированной теореме иерархии времени? (Можно ли использовать «иерархию размеров схемы», например?)$NEXP \not\subset ACC$

Методы зависят от модели и типа ресурса, для которого мы хотим получить нижнюю границу. Обратите внимание: чтобы доказать нижнюю границу сложности задачи, мы должны сначала исправить математическую модель вычислений: нижняя граница для состояния задачи состоит в том, что ни один алгоритм, использующий некоторое количество ресурсов, не может решить проблему, т. Е. Мы количественно определяем количественно над алгоритмами. Нам нужно иметь математическое определение области количественного определения. (Как правило, это верно для результатов невозможности.) Следовательно, результаты с нижней границей имеют место только для конкретной модели вычислений. Например, $\Omega(n \log n)$Нижняя граница для сортировки работает только для алгоритмов сортировки, основанных на сравнении, без этого ограничения и в более общих моделях вычислений может быть возможно решить сортировку быстрее, даже линейное время. (См. Комментарий Джоша ниже.)

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

I. Подсчет:

Идея: мы показываем, что есть больше функций, чем алгоритмы.

Пример: есть функции, которые требуют экспоненциально больших цепей.

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

II. Комбинаторные / Алгебраическая:

Идея: мы анализируем схемы и показываем, что они обладают определенным свойством, например, вычисляемые ими функции могут быть аппроксимированы некоторым классом математического объекта, в то время как целевая функция не обладает этим свойством.

$\mathsf{AC^0}$$\mathsf{AC^0}[p]$

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

В статье Разборова « О методе аппроксимации » утверждается, что метод аппроксимации завершен для доказательства нижних оценок в некотором смысле.

III. Диагонализация:

Идея. Диагонализируем по отношению к функциям меньшего класса. Идея восходит к Геделю (и даже Кантору).

Ex. Теоремы иерархии времени , теорема космической иерархии и т.д.

$\mathsf{P}$$\mathsf{PSpace}$$\mathsf{P}$$\mathsf{PSpace}$

У нас также есть барьер релятивизации (возвращаясь к Бейкеру, Гиллу и Соловаю) и барьер алгебраизации (Ааронсон и Вигдерсон), которые утверждают, что определенные типы аргументов диагонализации будут перенесены в другие параметры, где результат доказуемо ложен.

Обратите внимание, что эти барьеры не применяются к более общим аргументам диагонализации. Фактически, в работе Декстера Козена « Индексация субрекурсивных классов » диагонализация в завершена для доказательства нижних оценок.

Как вы, вероятно, заметили, существует тесная связь между поиском хороших универсальных симуляторов для класса сложности и отделением этого класса сложности от более крупных классов (формальное утверждение см. В статье Козена).

Последние работы

Для недавних авансов, проверьте последние бумаги Райана Уильямса . Я не обсуждаю их в этом ответе, так как надеюсь, что сам Райан напишет ответ.

Алгебраические деревья решений

Это не недавний метод, но достаточно мощный для определенных проблем.

$n$$d$

• $v$$q_v(x_1, \dots, x_n)$$d$$x_i-x_j$$i$$j$

• $-1$$0$$+1$

• $\{1,2,\dots,n\}$

$\vec{x}\in\mathbb{R}^n$

$\Omega(n^d)$

$\ell$$R(\ell) \subseteq \mathbb{R}^n$$\ell$$R(\ell)$$\mathbb{R}^n$$t = \text{depth}(\ell)$$d$$d$$(dt)^{O(n)}$

$W\subseteq\mathbb{R}^n$$d$$t$$W$$3^t (dt)^{O(n)}$$t = \Omega(\log \#W - n\log d)$

$n$$W$$n!$$n$$\Omega(n\log n)$

$\Omega(n\log n)$

$R(\ell)$$(dt)^{O(n)}$

$n^{O(n)}$$n\log n$

$\Omega(n^2)$$O(n^4\log n)$$2^{O(n)}$$\mathbb{R}^n$$n^4\log n$$k$$k$$k$$k$$O(n^{k/2})$$O(n^4\log n)$полиномы запросов; это время построения свободно в нижней модели.

Ура за двойной отрицательный результат!

У Manindra Agrawal есть хорошая статья «Доказательство нижних границ с помощью псевдослучайных генераторов». Это можно считать «темной лошадкой» в беге, чтобы доказать нижние границы, но статья интересна.

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

• Алгоритмы против нижних границ схемы Оливейра

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