# Complexity results for Lower-Elementary Recursive Functions?

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 .

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

: 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.

• The Wikipedia article you link to states that lower-elementary functions have polynomial growth (but it gives no reference.) Showing that a P-complete problem can or cannot be solved with elementary functions would be a good step towards pinning it down further. It does not, offhand, look impossible to simulate a Turing machine for n steps -- maybe a bounded sum corresponding to the number of steps of another bounded sum corresponding to each state transition? – Chris Pressey Dec 9 '12 at 11:32
• @Chris - My guess was that "polynomial growth" refers to the number of bits in the output being no more than linear in the number of bits in the input. I agree that the simulation seems very plausible, and seems doable in polynomial time (but might take some details to verify this!). – usul Dec 9 '12 at 17:22
• Sorry, that first part might not be clear, but it's because then on input of value $x$ the output has value at most polynomial in $x$. – usul Dec 9 '12 at 19:11
• Concerning question 3: the functions definable in the variant with $\log(x)$-bounded summation are all in the complexity class uniform $\mathsf{TC}^0$. With constant bounded summation you get a subclass of uniform $\mathsf{AC}^0$. – Jan Johannsen Dec 10 '12 at 10:15
• @Xoff I believe it is all in the summation: We are summing from $1$ to $x$, where (on an input of $n$ bits) $x$ can have size $2^n$, so our sum will be $2^n$ times the size of each summand. – usul Mar 27 '13 at 0:53

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.

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  that Boolean satisfiability SAT lies in the lowest level E0 of the Grzegorczyk Hierarchy, that is with bounded recursion instead of bounded summation.

 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 E0 to Lower Elementary
(and to generalize from SAT to QBFk for arbitrary but fixed k).

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