Алгоритмы с суперэкспоненциальным временем выполнения?

Я разговаривал со студентом на днях об общих классах сложности алгоритмов, таких как O (n), O (n ^k), O (n lg n), O (2 ⁿ), O (n!) и т.д. Я пытался придумать пример проблемы, для которой решения, наиболее известная время исполнения которых являются суперэкспоненциальными, такие как O (2 ^{2 ⁿ}), но все же разрешимый (например, не проблема с остановкой!) Единственный пример, который я знаю, - это выполнимость Presburger арифметики, что я не думаю, что какие-либо интро-CS-ученики действительно понимали бы или могли бы относиться к ним.

Мой вопрос: существует ли известная проблема, наиболее известное решение которой имеет сверхэкспоненциальное время исполнения; по крайней мере & omega; (n!) или & omega; (n ⁿ). Я действительно надеюсь, что существует некоторая "разумная" проблема, встречающая это описание, но я ничего не знаю.

Ответ 1

Maximum Parsimony - проблема поиска эволюционного дерева, связывающего n последовательностей ДНК (представляющих видов), которые требуют наименьших однонуклеотидных мутаций. N заданных последовательностей ограничены появлением у листьев; топология дерева и последовательности на внутренних узлах - это то, что мы можем выбрать.

В более CS-терминах: Нам дается куча строк длины-k, которые должны появляться у листьев какого-либо дерева, и нам нужно выбрать дерево, а также строку длины-k для каждый внутренний node в дереве, чтобы свести к минимуму сумму расстояния Хэмминга по всем краям.

Когда задано фиксированное дерево, оптимальное назначение последовательностей для внутренних узлов может быть определено очень эффективно, используя алгоритм Fitch. Но в обычном случае дерево не задано (т.е. Нас попросят найти оптимальное дерево), и это создает проблему NP-hard, что означает, что каждое дерево должно быть в принципе проверено. Несмотря на то, что эволюционное дерево имеет корень (представляющий гипотетического предка), нам нужно только рассмотреть отдельные неруковленные деревья, так как минимальное количество необходимых мутаций не зависит от положения корня. Для n видов имеются 3 * 5 * 7 *... * (2n-5) листовые меченые двоичные деревья. (Существует только одно такое дерево с тремя видами, у которого есть одна внутренняя вершина и 3 края, 4-й вид может быть вставлен на любом из трех краев для создания четкого дерева с 5 краями, 5-й вид может быть вставлен в любой из этих 5 ребер и т.д. - этот процесс генерирует все деревья ровно один раз.) Это иногда пишется (2n-5)!!, с!! что означает "двойной факториал".

На практике используется ветвь и граница, а на большинстве реальных наборов данных это позволяет избежать оценки большинства деревьев. Но для высоких "случайных" случайных данных требуется все или почти все (2n-5)!! деревья, которые нужно исследовать, поскольку в этом случае многие деревья имеют почти равные минимальные значения мутаций.

Ответ 2

Отображение всех перестановок строки длины n равно n!, нахождение гамильтонова цикла - это n!, минимальная окраска графа,....

Изменить: еще быстрее Функции Ackerman. На самом деле они кажутся без связанной функции.

A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.

from wiki:
A(4,3) = 2^2^65536,...

Ответ 3

Есть ли алгоритмы для вычисления действительных чисел с определенным количеством точности? Формула для области набора Мандельброта сходится крайне медленно; 10 ¹¹⁸ для двух цифр, 10 ¹¹⁸¹ терминов для трех.

Ответ 4

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

Колмогоровская сложность K (x) - это размер самой маленькой программы, которая выводит строку $x $на предопределенном универсальном компьютере U. Легко показать, что большинство строк не могут быть сжаты вообще (поскольку их больше строки длины n, чем программы длины n).
Если дать U максимальное время работы (скажем, некоторую полиномиальную функцию P), мы получаем ограниченную по времени колмогоровскую сложность. Тот же самый аргумент подсчета имеет место: есть некоторые строки, которые несжимаемы в это время ограниченной сложностью Колмогорова. Позвольте называть первую такую строку (некоторой длины n) x _P
Поскольку ограниченная по времени колмогоровская сложность вычислима, мы можем протестировать все строки и найти x _P
Поиск x _P не может быть выполнен за полиномиальное время, или мы могли бы использовать этот алгоритм для его сжатия, поэтому его поиск должен быть суперполиномиальной задачей. Мы знаем, что мы можем найти его в exp (P). (Перескакивая через некоторые технические детали)
Итак, теперь мы имеем временную E = exp (P). Мы можем повторить процедуру, чтобы найти x _E и т.д.

Этот подход дает нам разрешимую задачу супер-F для каждой строимой по времени функции F: найти первую строку длины n (некоторую большую константу), которая несжимаема по временному F.