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

Question

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

У меня вопрос , существует ли общеизвестная проблема, наиболее известное решение которой имеет суперэкспоненциальное время выполнения; не менее ω (n!) илиω (п ^п ).Я бы очень надеялся, что есть какое-то «разумное» решение этой проблемы, но я не знаю ни одной.

Answer 1

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

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

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

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

Answer 2

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

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

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,...

Answer 3

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

Answer 4

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

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

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