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)$

— 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

Odnośnie (bonusowego) pytania 3: wszystkie funkcje definiowane w wariancie z podsumowaniem związanym z znajdują się w klasie złożoności uniform . Wynika to z konstrukcji w Chandra, Stockmeyer i Vishkin „Stała głębokość redukcyjna”, SIAM J. Comput. 13 (1984), pokazują, że suma liczby bitów każdy może być obliczany za pomocą poynomial wielkości układów głębokość stale w większości bram. $\log(x)$ $\mathsf{TC}^0$ $n$ $n$

Przy stałym ograniczonym sumowaniu otrzymujesz podklasę uniform . Stałe ograniczanie sumowania można zredukować do dodawania i składu, a dodawanie można obliczyć za pomocą obwodów boolowskich o stałej głębokości, stosując metodę carry-lookahead. $\mathsf{AC}^0$

— Jan Johannsen
źródło

„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