Алгоритмы и теория структурной сложности

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

IP = PSPACE следует из рекурсивного алгоритма с эффективным использованием пространства, имитирующего интерактивные протоколы, и эффективного интерактивного протокола для оценки полностью количественных булевых формул. Фактически любое равенство классов сложности A = B можно рассматривать как следующее из двух эффективных алгоритмов (алгоритм для задач в A, эффективный по отношению к B, и наоборот).
Доказательством NP-полноты некоторой проблемы является просто нахождение эффективного алгоритма, который сводит к нему NP-полную проблему.
(Возможно!) Ключевой компонент в теореме иерархии времени - эффективная универсальная симуляция машин Тьюринга.
$\not \supset$
Теорема PCP состоит в том, что эффективное усиление зазора возможно для задач удовлетворения ограничений.
и т. д.

Мой вопрос (который, возможно, безнадежно расплывчатый!) Заключается в следующем: существуют ли какие-либо важные результаты в теории структурной сложности (в отличие от «мета-результатов», таких как барьер релятивизации), которые, как известно, не имеют естественной интерпретации в терминах эффективного алгоритмы (или протоколы связи)?

cc.complexity-theory structural-complexity Эшли Монтанаро
источник

Я вроде надеюсь, что ответ «нет», потому что я думаю, что сложность на самом деле заключается в понимании силы алгоритмов! Я собирался сказать, что PARITY не в почти соответствует требованиям, но сейчас я так не думаю. Вы можете рассматривать лемму о переключении как случайный алгоритм, который позволяет менять две строки схемы без увеличения размера (и даже может быть дерандомизирован ( eccc.hpi-web.de/report/2012/116 ).

A C^{0}

$AC^0$

Джошуа Грохов

Эшли Монтанаро: Возможно, теория сложности связана «по определению» с эффективностью алгоритмов (время / пространство). Как только вы уходите от эффективности, вы обнаруживаете фундаментальные результаты, такие как неразрешимость проблемы остановки, но вы больше не находитесь в области «сложности». Однако, пытаясь дать частичный ответ, я думаю, что логическая характеристика классов сложности является важным результатом, который дает иную перспективу, не (напрямую) связанную с «алгоритмами».

Марцио Де Биаси

В частности, я бы перечислил описательную характеристику NP с точки зрения экзистенциальной логики второго порядка. Это чисто выразительная сила, а не алгоритмы. Тем не менее, теорема Курселя предполагает, что это различие не является реальным.

Суреш Венкат

Не могли бы вы сказать, что доказательство Разборова-Смоленского PARITY не в AC0 содержит в своей основе алгоритмический результат? А как насчет нижних границ сложности запросов, таких как тот, который говорит, что квантовый компьютер не может решить проблему неупорядоченного поиска в запросах?

o (\sqrt{n})

$o(\sqrt{n})$

Робин Котари

см. также cstheory.stackexchange.com/questions/3229/…

sdcvvc

Ответы:

Для многих нижних оценок алгебраической сложности я не знаю естественной интерпретации в терминах эффективных алгоритмов. Например:

техника частных производных Нисана и Вигдерсона
рангово-гессенский метод Миньона и Рессера (задающий наиболее известную в настоящее время нижнюю границу перманента и детерминанта)
степень Штрассен (и Баур-Штрассен)
Техника связанных компонентов Ben-Or.

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

Для неалгебраических результатов, вот пара мыслей:

Стандартный аргумент подсчета для нижней границы сортировки видимому, не имеет интерпретации в терминах эффективных алгоритмов. Однако существует альтернативная версия этой нижней границы [1], в которой существует алгоритм, который, учитывая любое дерево решений, использующее слишком мало сравнений, эффективно создает список, который дерево решений сортирует неправильно. Но состязательный вариант, хотя и не сложный, значительно сложнее, чем счетное доказательство. (Обратите внимание, что это немного сильнее, чем то, что можно получить, применяя метод нижней границы противника, например, как в этих примечаниях , поскольку в [1] сам противник эффективен .) $n \log n$
Я думаю, что я изменил свое мнение о PARITY не в (даже оригинальное доказательство, не говоря уже о доказательстве Разборова-Смоленского, как указано @RobinKothari). Хотя лемму о переключении можно рассматривать как рандомизированный ( или детерминированный ) алгоритм, который позволяет менять две строки схемы без большого увеличения размера, я думаю, что это действительно отличается от многих результатов по сложности, и особенно те, которые вы цитируете. Например, доказательство Уильямса, что , основано на существовании хорошего алгоритма для конкретной задачи. Напротив, если бы можно было доказать что-то вроде леммы о переключении неконструктивно, это было бы так же хорошо для доказательства PARITY, а не в . $AC^0$ $ACC \neq NEXP$ $AC^0$

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

[1] Аталла М.Дж. и Косараджу С.Р. Нижняя граница для сортировки на основе противника . Поставить в известность. Proc. Lett. 13 (2): 55-57, 1981.

Джошуа Грохов
источник