Wyniki dotyczące złożoności funkcji rekurencyjnych o niższych elementach?

Zaintrygowany ciekawym pytaniem Chrisa Presseya na temat funkcji elementarno-rekurencyjnych badałem więcej i nie mogłem znaleźć odpowiedzi na to pytanie w Internecie.

Te podstawowe funkcje rekurencyjne odpowiadają dobrze wykładniczemu hierarchii . $\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots$

Z definicji wydaje się proste, że problemy decyzyjne rozstrzygalne (termin?) Za pomocą funkcji niższych elementów powinny być zawarte w EXP, aw rzeczywistości w DTIME ; funkcje te są również ograniczone do ciągów wyjściowych liniowych na długości wejściowej [1]. $(2^{O(n)})$

Ale z drugiej strony nie widzę żadnych oczywistych dolnych granic; na pierwszy rzut oka wydaje się możliwe, że NIŻSZY ELEMENTARNY może ściśle zawierać NP, a może nie zawierać pewnych problemów w P, lub najprawdopodobniej pewnej możliwości, której jeszcze nie wyobrażałem. Byłoby niesamowicie fajnie, gdyby LOWER-ELEMENTARY = NP, ale przypuszczam, że to zbyt wiele, o co należy prosić.

Więc moje pytania:

Czy moje dotychczasowe zrozumienie jest prawidłowe?
Co wiadomo o klasach złożoności ograniczających niższe elementarne funkcje rekurencyjne?
(Bonus) Czy podczas wprowadzania dalszych ograniczeń funkcji rekurencyjnych mamy jakieś przyjemne charakterystyki klasy złożoności? Myślałem w szczególności o ograniczeniu do podsumowań związanych z , które - jak sądzę - przebiegają w czasie wielomianowym i dają wynik liniowy; lub sumowania o stałych ograniczeniach, które, jak sądzę, przebiegają w czasie wielomianowym i dają wynik o długości co najwyżej . $\log(x)$ $n + O(1)$

[1]: Możemy pokazać (uważam), że funkcje niższych elementów podlegają tym ograniczeniom przez indukcję strukturalną, zakładając, że funkcje mają złożoność i wyniki długość bitowa na wejściu o długości . Gdy , pozwalając , każdy ma wynik o długości , więc ma - długość wejściowa (a zatem wyjściowa długość ); złożoność obliczenia wszystkich s wynosi a wynosi $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)}$ , więc ma złożoność i wyjście o długości jak zastrzeżono. $f$ $2^{O(n)}$ $O(n)$

Gdy , mają wyjścia o długości , więc wartość sumy wyjść wynosi , więc ich suma ma długość . Złożoność sumowania tych wartości jest ograniczona przez (liczba sumowań) razy (złożoność każdego dodania) dając , a złożoność obliczania wyników jest ograniczona przez (liczba obliczeń) razy (złożoność każdego z nich), dając . Więc ma złożoność $f(x) = \sum_{i=1}^x g(x)$ $g$ $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)}$ i wydajność o długości jak zastrzeżono. $O(n)$

cc.complexity-theory reference-request complexity-classes computability usul
źródło

Artykuł w Wikipedii, do którego linkujesz, stwierdza, że funkcje niższych elementów mają wzrost wielomianowy (ale nie zawiera odniesienia). Wykazanie, że problem P-zupełny można lub nie można rozwiązać za pomocą funkcji elementarnych, byłby dobrym krokiem w kierunku dalszego jego dokładnego określenia. Odręcznie nie wydaje się niemożliwa symulacja maszyny Turinga dla n kroków - może ograniczona suma odpowiadająca liczbie kroków innej ograniczonej sumy odpowiadającej każdemu przejściu stanu?

Chris Pressey,

@Chris - Domyślam się, że „wzrost wielomianowy” odnosi się do liczby bitów na wyjściu, która jest nie większa niż liniowa liczba bitów na wejściu. Zgadzam się, że symulacja wydaje się bardzo prawdopodobna i wydaje się wykonalna w czasie wielomianowym (ale może to wymagać pewnych szczegółów, aby to zweryfikować!).

usul

Przepraszam, ta pierwsza część może nie być jasna, ale dlatego, że wtedy na wejściu wartości wyjście ma wartość co najwyżej wielomianową w .

x

$x$

x

$x$

usul

Odnośnie do pytania 3: wszystkie funkcje definiowane w wariancie z podsumowaniem są wszystkie w klasie złożoności uniform . Przy stałym ograniczonym sumowaniu otrzymujesz podklasę uniform .

\log (x)

$\log(x)$

{T C}^{0}

$\mathsf{TC}^0$

{A C}^{0}

$\mathsf{AC}^0$

Jan Johannsen,

@Xoff Myślę, że to wszystko w podsumowaniu: sumujemy od do , gdzie (na wejściu bitów) może mieć rozmiar , więc nasza suma będzie razy większa od wielkości każdego sumy .

1

$1$

x

$x$

n

$n$

x

$x$

2^{n}

$2^n$

2^{n}

$2^n$

usul

„Dolne funkcje elementarne są w EXP ” jest poprawne. W rzeczywistości znajdują się w DPSPACE ( n ); jak widać na przykład z indukcji strukturalnej.
Pokazano tutaj [1], że logiczna satysfakcja SAT leży na najniższym poziomie E ₀ Hierarchii Grzegorczyka, to znaczy z ograniczoną rekurencją zamiast ograniczonego sumowania.

[1] Cristian Grozea: Obliczenia predykatów NP w najsłabszym poziomie hierarchii Grzegorczyck (sic!). Journal of Automata, Languages and Combinatorics 9 (2/3) : 269-279 (2004).

Podstawowym założeniem jest to, aby zakodować podanego wzoru binarnego o długości n do liczby całkowitej N o wartości w przybliżeniu wykładniczej w N ; a następnie wyrazić istnienie zadowalającego zadania w kategoriach kwantyfikacji ograniczonej przez wspomniany N (a nie n ).

Ta metoda wydaje się przenosić z E ₀ na niższy elementarny
(i uogólniać z SAT na QBF _k dla dowolnego, ale ustalonego k ).

Nie oznacza to jednak, że E ₀ zawiera NP (a nawet P w tym przypadku), ponieważ wiadomo, że obliczenia czasu polimetrii pozostawiają E ₂ .

Martin Ziegler
źródło

Wyniki dotyczące złożoności funkcji rekurencyjnych o niższych elementach?

Odpowiedzi: