<p>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 <a href="http://dx.doi.org/10.1137/0213027">Chandra, Stockmeyer and Vishkin "Constant depth reducibility", SIAM J. Comput. 13 (1984)</a> showing that the sum of $n$ numbers of $n$ bits each can be computed by poynomial size constant depth circuits with majority gates.</p>

<p>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. </p>

CC BY-SA 3.0
2012-12-12T09:28:34.373Z
2012-12-12T09:28:34.373Z
Jan Johannsen
<ol>
<li><p>"Lower elementary functions are in <b>EXP</b>" is correct. 
They are in fact in <b>DPSPACE</b>(<i>n</i>);
as can for instance be seen from structural induction.</p></li>
<li><p>It is shown here [1] that Boolean satisfiability SAT lies in the lowest level
<b>E</b><sub>0</sub> of the Grzegorczyk Hierarchy, that is with bounded recursion instead of bounded summation.</p></li>
</ol>

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

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

<p>This method seems to carry over from <b>E</b><sub>0</sub> to <i>Lower Elementary</i><br>
(and to generalize from SAT to QBF<sub><i>k</i></sub>
for arbitrary but fixed <i>k</i>).</p>

<p>It does not imply <b>E</b><sub>0</sub> to contain <b>NP</b> (or even <b>P</b> for that matter), 
though, because polytime computations are known to leave <b>E</b><sub>2</sub>.</p>

CC BY-SA 3.0
2013-09-30T08:07:52.637Z
2013-09-30T08:13:49.353Z
2013-09-30T08:13:49.353Z
Martin Ziegler
<p>Since lower elementary functions are computable in time <span class="math-container">$2^{O(n)}$</span> (and space <span class="math-container">$O(n)$</span>), the set of corresponding decision problems is unlikely to include NP, or even just <span class="math-container">$\mathrm{NTIME}(n^{1+\epsilon})$</span> for a constant <span class="math-container">$\epsilon&gt;0$</span>. 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 <span class="math-container">$\mathrm{DTIME}(n^{1+\epsilon})$</span> is unlikely to be included in <span class="math-container">$\mathrm{DSPACE}(n)$</span>.</p>

CC BY-SA 4.0
2023-06-28T06:19:06.633Z
2023-06-28T06:19:06.633Z
Emil Jeřábek
<p>Intrigued by Chris Pressey's interesting <a href="https://cstheory.stackexchange.com/questions/14641/simply-stated-restriction-on-imperative-programming-language-that-captures-the-e">question on elementary-recursive functions</a>, I was exploring more and unable to find an answer to this question on the web.</p>

<p>The <a href="http://en.wikipedia.org/wiki/ELEMENTARY" rel="nofollow noreferrer">elementary recursive functions</a> correspond nicely to the exponential hierarchy, $\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots$.</p>

<p>It seems straightforward from the definition that decision-problems decidable (term?) by <a href="http://en.wikipedia.org/wiki/ELEMENTARY#Lower_elementary_recursive_functions" rel="nofollow noreferrer"><em>lower</em>-elementary functions</a> 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].</p>

<p>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.</p>

<p>So my questions:</p>

<ol>
<li>Is my understanding so far correct?</li>
<li>What is known about the complexity classes bounding the lower elementary recursive functions?</li>
<li>(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)$.</li>
</ol>

<hr>

<p>[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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-12-09T11:32:10.937Z
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
CC BY-SA 3.0
2012-12-09T17:22:59.050Z
@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
CC BY-SA 3.0
2012-12-09T19:11:03.300Z
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
CC BY-SA 3.0
2012-12-10T10:15:22.603Z
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
CC BY-SA 3.0
2012-12-11T20:35:52.537Z
@Jan thanks! Also, do you know of any references where these questions are discussed? (Papers or texts.)
usul
CC BY-SA 3.0
2013-03-24T09:13:07.490Z
What would prevent you to use a polynomial computation time $P(n)$ instead of $2^n$ in your proof ?
Xoff
CC BY-SA 3.0
2013-03-27T00:53:58.997Z
@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
<cc.complexity-theory><reference-request><complexity-classes><computability>
Complexity results for Lower-Elementary Recursive Functions?
usul
# Complexity results for Lower-Elementary Recursive Functions?

(Asked by: username_0 on 2012-12-08)

Intrigued by Chris Pressey's interesting [question on elementary-recursive functions](https://cstheory.stackexchange.com/questions/14641/simply-stated-restriction-on-imperative-programming-language-that-captures-the-e), I was exploring more and unable to find an answer to this question on the web.

The [elementary recursive functions](http://en.wikipedia.org/wiki/ELEMENTARY) 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](http://en.wikipedia.org/wiki/ELEMENTARY#Lower_elementary_recursive_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.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, computability
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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!).  
> **username_0**: 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$.  
> **username_2**: 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$.  
> **username_0**: @Jan thanks! Also, do you know of any references where these questions are discussed? (Papers or texts.)  
> **username_3**: What would prevent you to use a polynomial computation time $P(n)$ instead of $2^n$ in your proof ?  
> **username_0**: @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.  

---

## 3 answers

### Answer by username_2 on 2012-12-12. Score: 7

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)](http://dx.doi.org/10.1137/0213027) 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 by username_4 on 2013-09-30. Score: 5

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

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


---

### Answer by username_5 on 2023-06-28. Score: 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)$.


---

