Появляются ли функции с более медленным ростом, чем обратный Аккерманн, в границах времени выполнения?

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

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

reference-request algorithm-analysis time-complexity runtime-analysis user2566092
источник

O (1)

$O(1)$ время алгоритмы? Вы спрашиваете об известной проблеме, наиболее известным алгоритмом которой является

? Сначала вам нужно найти функцию, которая растет «существенно быстрее», чем

, например, TREE

, а затем взять ее обратное, а затем найти проблему, которая подходит ей!

ω (1)

$\omega(1)$

o (α (n))

$o(\alpha(n))$

A (n)

$A(n)$

(n)

$(n)$

Пол Г.Д.

Есть произвольные надуманные алгоритмы, построенные из временной иерархии thm

vzn 19.09.13

@vzn: Любое

не конструируемо по времени (включая

). Таким образом, теорема о временной иерархии не может быть использована здесь.

f (n) = o (n)

$f(n) = o(n)$

α (n)

$\alpha(n)$

mdxn

@mdx рад, что кто-то указал на это, просто тестирую тебя. да в последнее время было мышление могло быть обобщением времени THM иерархии для суб-

функций. но, в любом случае, предел

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

o (n)

$o(n)$

o (n)

$o(n)$

o (n)

$o(n)$

ВЗН

@vzn: ОП действительно нужно уточнить, какую модель вычислений они имеют в виду.

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

DLOGTIME

$\text{DLOGTIME}$

LH

$\text{LH}$

mdxn

Ответы:

Сет Петти придумал алгоритм для вычисления чувствительности минимального остовного дерева во времени , улучшив алгоритм Тарьяна, который вычисляет то же самое во времени . (Сравните это с алгоритмом Шазеля для вычисления минимального остовного дерева $O(m\log \alpha(m,n))$ $O(m\alpha(m,n))$ $O(m\alpha(m,n))$ сама.) Проблема чувствительности требует вычислить для данного графика и заданного минимального остовного дерева то, насколько может измениться каждый вес ребра без изменения минимального остовного дерева.

(Спасибо Цви Копеловиц за эту ссылку.)

Юваль Фильмус
источник

Я не знаю, является ли обратный логарифм Аккерманна «существенно медленнее», чем обратный Аккерманн, но я нашел такой вид времени выполнения удивительным.

Юваль Фильмус

$\alpha^*(n)$ $n$

templatetypedef
источник

-1

Когда Алан Тьюринг обнаружил компьютер, предлагалось несколько моделей для этого компьютера. Тьюринг доказал, что некоторые (3) из этих моделей могут моделировать друг друга и вычислять функцию Аккермана, тогда как другие модели могут моделировать друг друга, но не функцию Аккермана (поэтому они не могли моделировать 3). Поэтому эти 3 модели (машина Тьюринга, фон Нейман и одна, которую я не знаю) были выбраны в качестве архитектуры для компьютера. Это не означает, что функция Аккермана - это предел компьютера, но я полагаю, что это сложная наука. Мне неизвестны какие-либо вычислимые функции, которые растут быстрее, чем функция Аккермана.

Я не думаю, что есть практическая проблема, которая соответствует вашему вопросу, но, возможно, мы сможем ее решить. Мы должны наложить ограничения на вход, хотя. Поскольку мы не можем использовать O (n), мы не можем проверить весь ввод. На самом деле, мы даже не можем проверить длину ввода, так как это будет O (log n). Итак, нам нужно в качестве первого параметра представить длину остальной части входных данных, например, c, так что Ackermann (c) - это длина входных данных. Поскольку это также не подходит, мы требуем в качестве первого значения на нашем входе параметр c, так что bb (c) примерно равна длине входа, где bb - функция занятого бобра. Эта функция не вычислима, но bb (c), безусловно, существует. Затем алгоритм выглядит так:

for (int i=0; i<c; i++) {
    if (input[i] == null) {
        return false;
    }
}
return true;

Цель алгоритма состоит в том, чтобы проверить, что если c является обратным к bb, то если входная длина больше, чем bb (c).

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

Альберт Хендрикс
источник

Определенно существуют функции, которые растут быстрее, чем функция Аккермана, как указано в комментариях (TREE (n)). Сложная часть вопроса заключается в построении алгоритма с ограничением времени выполнения обратной функции. Такая машина не имеет достаточно времени для вычисления обратного функции в первую очередь, поэтому конструкция TM, которая достигает этого, не является прямой.

mdxn