Complexity results for Lower-Elementary Recursive Functions?

Question

Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web.

The elementary recursive functions correspond nicely to the exponential hierarchy, $\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots$.

It seems straightforward from the definition that decision-problems decidable (term?) by lower-elementary functions should be contained in EXP, and in fact in DTIME$(2^{O(n)})$; these functions also are constrained to output strings linear in their input length [1].

But on the other hand, I don't see any obvious lower bounds; at first glance it seems conceivable that LOWER-ELEMENTARY could strictly contain NP, or perhaps fail to contain some problems in P, or most likely some possibility I've not yet imagined. It would be epicly cool if LOWER-ELEMENTARY = NP but I suppose that is too much to ask for.

So my questions:

1. Is my understanding so far correct?
2. What is known about the complexity classes bounding the lower elementary recursive functions?
3. (Bonus) Do we have any nice complexity-class characterizations when making further restrictions on recursive functions? I was thinking in particular of the restriction to $\log(x)$-bounded summations, which I think run in polynomial time and produce linear output; or constant-bounded summations, which I think run in polynomial time and produce output of length at most $n + O(1)$.

---

[1]: We can show (I believe) that lower-elementary functions are subject to these restrictions by structural induction, supposing that the functions $h,g_1,\dots,g_m$ have complexity $2^{O(n)}$ and outputs of bitlength $O(n)$ on an input of length $n$. When $f(x) = h(g_1(x),\dots,g_m(x))$, letting $n := \log x$, each $g$ has output of length $O(n)$, so $h$ has an $O(n)$-length input (and therefore $O(n)$-length output); the complexity of computing all $g$s is $m2^{O(n)}$ and of $h$ is $2^{O(n)}$, so $f$ has complexity $2^{O(n)}$ and output of length $O(n)$ as claimed.

When $f(x) = \sum_{i=1}^x g(x)$, the $g$s have outputs of length $O(n)$, so the value of the sum of outputs is $2^n 2^{O(n)} \in 2^{O(n)}$, so their sum has length $O(n)$. The complexity of summing these values is bounded by $2^n$ (the number of summations) times $O(n)$ (the complexity of each addition) giving $2^{O(n)}$, and the complexity of computing the outputs is bounded by $2^{n}$ (the number of computations) times $2^{O(n)}$ (the complexity of each one), giving $2^{O(n)}$. So $f$ has complexity $2^{O(n)}$ and output of length $O(n)$ as claimed.

Answer 1

Concerning (bonus) question 3: the functions definable in the variant with $\log(x)$-bounded summation are all in the complexity class uniform $\mathsf{TC}^0$. This follows from the construction in Chandra, Stockmeyer and Vishkin "Constant depth reducibility", SIAM J. Comput. 13 (1984) showing that the sum of $n$ numbers of $n$ bits each can be computed by poynomial size constant depth circuits with majority gates.

With constant bounded summation you get a subclass of uniform $\mathsf{AC}^0$. Constant bounded summation can be reduced to addition and composition, and addition can be computed by constant depth boolean circuits using the carry-lookahead method.

Answer 2

1. "Lower elementary functions are in EXP" is correct. They are in fact in DPSPACE(n); as can for instance be seen from structural induction.

2. It is shown here [1] that Boolean satisfiability SAT lies in the lowest level E₀ of the Grzegorczyk Hierarchy, that is with bounded recursion instead of bounded summation.

[1] Cristian Grozea: NP Predicates Computable in the Weakest Level of the Grzegorczyck (sic!) Hierarchy. Journal of Automata, Languages and Combinatorics 9(2/3): 269-279 (2004).

The basic idea is to encode the given formula of binary length n into an integer N of value roughly exponential in n; and then express the existence of a satisfying assignment in terms of quantification bounded by said N (rather than n).

This method seems to carry over from E₀ to Lower Elementary
(and to generalize from SAT to QBF_k for arbitrary but fixed k).

It does not imply E₀ to contain NP (or even P for that matter), though, because polytime computations are known to leave E₂.

Answer 3

Since lower elementary functions are computable in time $2^{O(n)}$ (and space $O(n)$), the set of corresponding decision problems is unlikely to include NP, or even just $\mathrm{NTIME}(n^{1+\epsilon})$ for a constant $\epsilon>0$. This would require a deterministic simulation of nondeterministism considerably more efficient (wrt time and space) than what is currently known, and what is expected to be possible. In fact, even $\mathrm{DTIME}(n^{1+\epsilon})$ is unlikely to be included in $\mathrm{DSPACE}(n)$.