Какие проблемы, когда мы знаем, что у нас есть оптимальный алгоритм?

Каковы некоторые нетривиальные задачи, в которых мы знаем, что текущий алгоритм, который у нас есть, является асимптотически оптимальным? (Для машин Тьюринга)

И как это доказано?

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

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

Недостатком, однако, является то, что эта мера сложности почти исключительно используется в квантовой обработке информации, поскольку она обеспечивает простой способ доказать разрыв между квантовой и классической вычислительной мощью. Наиболее известным квантовым алгоритмом в этой структуре является алгоритм Гровера . Для заданной двоичной строки для которой существует один i такой, что x i = n , необходимо найти i . Классически (без квантового компьютера) наиболее тривиальный алгоритм является оптимальным: вам нужно запросить эту строку в среднем n / 2 раза, чтобы найти$x_1,\dots ,x_n$$i$$x_i=n$$i$$n/2$ . Гровер представил квантовый алгоритм, который делает это в O ( $i$запросы к строке. Это также оказалось оптимальным.$O(\sqrt n)$

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

1. Сортировка сравнений с использованием сравнений (сортировка слиянием, чтобы назвать одно) является оптимальной, доказательство заключается в простом вычислении высоты дерева с помощью n ! уходит.$O (n \log n)$$n!$

2. Предполагая гипотезу об уникальных играх, Хот, Киндлер, Моссель и О'Доннелл показали, что NP-завершено, чтобы приблизить Max-Cut лучше, чем алгоритм Гоманса и Уильямсона. Таким образом, в этом смысле G & W является оптимальным (при условии, что ).$P\neq NP$

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

Предположим , вы получаете вход и просят решить , если RAM машина M Завершает на входе х после т шагов. Согласно теореме временной иерархии, оптимальный алгоритм для решения этой проблемы состоит в том, чтобы моделировать выполнение M ( x ) для t шагов, что можно сделать за время O ( t ) .$w = \langle M, x, t \rangle$$M$$x$$t$$M(x)$$t$$O(t)$

(Примечание: для машин Тьюринга моделирование выполнения занимает O ( t log t ) шагов; мы знаем только нижнюю границу Ω ( t ) . Таким образом, это не совсем оптимально для машин Тьюринга конкретно).$M$$O(t \log t)$$\Omega(t)$

Есть некоторые другие проблемы, которые содержат версию проблемы остановки в качестве дополнительного случая. Например, решение, является ли предложение следствием WS1S, занимает время 2 ↑ ↑ O ( | θ | ), и это оптимально.$\theta$$2 \uparrow \uparrow O(|\theta|)$

Я не уверен, что вы подразумеваете под "нетривиальным", но как насчет этого? . Этот язык не является регулярным, поэтому любой TM, решающий, что он должен работать в Ω ( n log n ) . Простой алгоритм (пересекающий все остальные 0) является оптимальным.$L = \{0^{2^k} | k \geq 0\}$$\Omega(n \log n)$

Если вы допускаете проблемы с динамической структурой данных, мы знаем некоторые суперлинейные оптимальные по времени алгоритмы. Это в модели клеточного зонда, которая так же сильна, как слово RAM, т.е. это не ограниченная модель, такая как алгебраические деревья решений.

Одним из примеров является хранение сумм префиксов при динамическом обновлении. Мы начнем с массива чисел , и цель состоит в том, чтобы сохранить структуру данных, которая позволяет выполнять следующие операции:$A[1], \ldots, A[n]$

• Добавить к A [ i ] , учитывая i и $\Delta$$A[i]$$i$$\Delta$
• $\sum_{j = 1}^i{A[i]}$$i$

$O(\log n)$$A[i]$$n$$\Omega(n\log n)$

$\{1, \ldots n\}$

• $i$$j$$i$$j$
• $i$$i$

$O(\alpha(n))$$\alpha$$n$$\Omega(n\alpha(n))$

Многие потоковые алгоритмы имеют верхние границы, совпадающие с их нижними границами.

Есть два схожих алгоритма поиска, которые, насколько я понимаю, являются оптимальными, основаны на конкретных ограничениях на порядок / распределение входных данных. однако представления алгоритмов обычно не подчеркивают эту оптимальность.

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

• Бинарный поиск находит точку в логарифмическом времени в среднем в отсортированном списке, но требует сортировки входных данных.

^{Я цитирую Википедию выше, но у нее нет доказательств того, что они оптимальны, может быть, некоторые другие ссылки, которые доказывают оптимальность, могут быть найдены аудиторией.}

Многие сублинейные алгоритмы времени имеют верхние границы, соответствующие их нижним границам.