Результаты сложности для низкоэлементарных рекурсивных функций?

Заинтригованный интересным вопросом Криса Пресси об элементарно-рекурсивных функциях , я изучал больше и не мог найти ответ на этот вопрос в Интернете.

В Элементарные рекурсивные функции соответствуют хорошо экспоненциальной иерархии, $\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots$ ,

Это кажется простым из определения, решение , проблемы неразрешимы (термин?) По более низким -элементарным функциям должен содержаться в EXP, а на самом деле в DTIME $(2^{O(n)})$ ; эти функции также ограничены линейными по длине выходными строками [1].

Но с другой стороны, я не вижу очевидных нижних границ; на первый взгляд кажется вполне вероятным, что LOWER-ELEMENTARY может строго содержать NP, или, возможно, не содержать некоторые проблемы в P, или, скорее всего, возможность, которую я еще не представил. Было бы невероятно круто, если LOWER-ELEMENTARY = NP, но я полагаю, это слишком много, чтобы просить.

Итак, мои вопросы:

Правильно ли мое понимание?
Что известно о классах сложности, ограничивающих нижние элементарные рекурсивные функции?
(Бонус). Имеем ли мы какие-либо хорошие характеристики класса сложности, когда накладываем дополнительные ограничения на рекурсивные функции? Я думал, в частности, об ограничении $\log(x)$ -ограниченные суммирования, которые, как мне кажется, выполняются за полиномиальное время и дают линейный результат; или суммированные с константами суммирования, которые, я думаю, выполняются за полиномиальное время и дают результат длины не более $n + O(1)$ ,

[1]: Мы можем показать (я полагаю), что нижние элементарные функции подчиняются этим ограничениям структурной индукцией, предполагая, что функции $h,g_1,\dots,g_m$ иметь сложность $2^{O(n)}$ и выходы битовой длины $O(n)$ на входе длины $n$ , когда $f(x) = h(g_1(x),\dots,g_m(x))$ , позволяя $n := \log x$ каждый $g$ имеет вывод длины $O(n)$ , так $h$ имеет $O(n)$ длина ввода (и, следовательно, $O(n)$ длина выхода); сложность вычисления всего $g$ с это $m2^{O(n)}$ и из $h$ является $2^{O(n)}$ , так $f$ имеет сложность $2^{O(n)}$ и вывод длины $O(n)$ как заявлено.

когда $f(x) = \sum_{i=1}^x g(x)$ , $g$ s имеют выходы длины $O(n)$ Таким образом, значение суммы выходов $2^n 2^{O(n)} \in 2^{O(n)}$ поэтому их сумма имеет длину $O(n)$ , Сложность суммирования этих значений ограничена $2^n$ (количество сумм) раз $O(n)$ (сложность каждого сложения) дача $2^{O(n)}$ и сложность вычисления выходов ограничена $2^{n}$ (количество вычислений) раз $2^{O(n)}$ (сложность каждого), давая $2^{O(n)}$ , Так $f$ имеет сложность $2^{O(n)}$ и вывод длины $O(n)$ как заявлено.

cc.complexity-theory reference-request complexity-classes computability усул
источник

В статье в Википедии, на которую вы ссылаетесь, говорится, что у низкоэлементарных функций есть полиномиальный рост (но в ней нет ссылок). Показано, что P-полная задача может или не может быть решена с помощью элементарных функций, будет хорошим шагом к дальнейшему ее закреплению. На первый взгляд не представляется невозможным смоделировать машину Тьюринга для n шагов - может быть, ограниченная сумма, соответствующая числу шагов другой ограниченной суммы, соответствующей каждому переходу состояния?

Крис Пресси

@Chris - я предположил, что «полиномиальный рост» относится к числу битов в выходных данных, которое является не более чем линейным по числу битов на входе. Я согласен, что симуляция кажется очень правдоподобной и выполнимой за полиномиальное время (но для подтверждения этого могут потребоваться некоторые детали!).

Усул

Извините, эта первая часть может быть неясной, но это потому, что при вводе значения

x

$x$ выход имеет значение не более полинома в

x

$x$ ,

Усул

По вопросу 3: функции, определяемые в варианте с

\log (x)

$\log(x)$ суммирование все в форме класса сложности

{T C}^{0}

$\mathsf{TC}^0$ , С постоянным ограниченным суммированием вы получите подкласс равномерного

{A C}^{0}

$\mathsf{AC}^0$ ,

Ян Йоханнсен

@Xoff Я полагаю, что все в суммировании: мы суммируем

1

$1$ в

x

$x$ где (на входе

n

$n$ бит)

x

$x$ может иметь размер

2^{n}

$2^n$ так наша сумма будет

2^{n}

$2^n$ раз размер каждого слагаемого.

Усул

«Нижние элементарные функции в EXP » - это правильно. На самом деле они находятся в DPSPACE ( n ); как это видно, например, из структурной индукции.
Здесь показано [1], что булева выполнимость SAT лежит на самом низком уровне E ₀ иерархии Гжегорчика, то есть с ограниченной рекурсией вместо ограниченной суммирования.

[1] Кристиан Грозеа: NP Предикаты, вычислимые в самом слабом уровне иерархии Гжегорчика (sic!). Журнал автоматов, языков и комбинаторики 9 (2/3) : 269-279 (2004).

Основная идея состоит в том, чтобы закодировать данную формулу двоичной длины n в целое число N, значение которого примерно равно экспоненте в n ; а затем выразить существование удовлетворительного присваивания в терминах количественного определения, ограниченного указанным N (а не n ).

Этот метод, кажется, переносит с E ₀ на младший элементарный
(и обобщает с SAT на QBF_k для произвольного, но фиксированного k ).

Тем не менее, это не означает, что E ₀ содержит NP (или даже P в этом отношении), поскольку, как известно, вычисления с временным интервалом оставляют E ₂ .

Мартин Циглер
источник

Результаты сложности для низкоэлементарных рекурсивных функций?

Ответы: