Нижние оценки на сложность задач

[mihaild]

Как известно, доказывать нижние оценки "что-то нельзя сделать быстрее чем за такое-то время" сложно. Найти обзор результатов такого вида не удалось - может быть кто-то такой знает? Или просто какие-то еще интересные примеры?
Известные мне примеры:
0. Теорема об иерархии по времени (позволяет получать довольно близкие верхние и нижние оценки, но для очень страных задач).
1. Сортировка через сравнения (и наверное тут можно придумать еще кучу задач с условием, задаваемым оракулом, где можно получить нижнюю оценку через необходимое количество информации).
2. Система непересекающихся множеств - нельзя получить амортизационную сложность лучше чем $\alpha(m, n)$, а такую - можно.
3. В работе Thorup есть загадочное утверждение "Linear Dijkstra $\Leftrightarrow$ linear sorting, Thorup'96", но найти эту работу (или хотя бы точную формулировку) мне не удалось.

[grizzly]

mihaild в сообщении #1219924 писал(а):

но найти эту работу (или хотя бы точную формулировку) мне не удалось

Эту, наверное?

[Narn]

Сейчас еще модно условные результаты получать, причем для полиномиальных задач. Грубо говоря, предполагая, например, что SAT меньше чем за $O(2^n)$ не решается, доказываем, что что-то не решается за субквадратное или сублинейное время (а квадратичный или линейный алгоритм уже могут быть известны). Ключевые слова Exponential Time Hypothesis, Strong Exponential Time Hypothesis (ETH, SETH), Hardness in P. Например, вот эта работа о расстоянии Фреше https://arxiv.org/abs/1404.1448, еще на странице Вирджинии Уильямс есть полезные ссылки https://people.csail.mit.edu/virgi/.

[Xaositect]

mihaild в сообщении #1219924 писал(а):

2. Система непересекающихся множеств - нельзя получить амортизационную сложность лучше чем $\alpha(m, n)$, а такую - можно.
3. В работе Thorup есть загадочное утверждение "Linear Dijkstra $\Leftrightarrow$ linear sorting, Thorup'96", но найти эту работу (или хотя бы точную формулировку) мне не удалось.

Такого рода результаты обычно доказываются в модели, где сложность считается по доступу к памяти. Ищите по ключевым словам cell probe complexity.

[Sender]

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

[mihaild]

Сколько всего умные люди напридумывали. Спасибо, буду изучать.

[Xaositect]

Собственно, как такие оценки доказывать - это остовной вопрос теории сложности вычислений. А посколько просто не получилось, то сейчас есть много разных моделей, либо ограниченных, в которых иногда доказываются сильные результаты, как та же монотонная сложность, либо общих, где можно доказать хоть что-то, как правило либо не сильно отличающееся от размера входа, либо как-то зависящее от параметров модели.
Я упомяну еще пару областей, знакомых мне:
В схемной сложности совсем недавно питерцы и Find доказали нижнюю оценку $(3 + \frac{1}{86}) n$: https://eccc.weizmann.ac.il/report/2015/166/ , там можно посмотреть ссылки на предыдущие результаты.
В алгебраической сложности есть разные результаты, есть книга Burgisser, Clausen, Shokrollahi "Algebraic Complexity Theory", но она уже достаточно старая, там нет, например, новых результатов Landsberg-Ressayre по перманенту и Landsberg-Mihalek по матричному умножению. Можно смотреть статьи Landsberg'а, Ikenmeyer'а и Mulmuley и на что они ссылаются. У Ландсберга скоро выйдет книга "Geometry and Complexity Theory".
Есть еще результаты в области communication complexity, где считается обмен сообщений между двумя агентами, кооперирущимися для проведения вычисления. У этих результатов есть разные приложения в других областях, например для глубины схем или для машин Тьюринга (где можно выделить агентов сидящих на разных концах ленты, соответственно один акт коммуникации будет иметь сложность $O(n)$).