<p>The Petri nets/Vector Addition Systems reachability problem is not primitive recursive; more precisely, it is complete for the class <span class="math-container">$\mathcal F_\omega$</span> of the fast-growing hierarchy (essentially the complexity of the Ackermann function). This was shown recently by <a href="https://arxiv.org/abs/2104.12695" rel="noreferrer">Leroux</a> and <a href="https://arxiv.org/abs/2104.13866" rel="noreferrer">Czerwiński and Orlikowski</a>, settling a problem that has been open for decades.</p>

CC BY-SA 4.0
2023-10-13T20:31:44.973Z
Not strictly related to the topic but a good reference for problems beyond elementary is the survey by Sylvain Schmitz (https://dl.acm.org/doi/10.1145/2858784)
Bartosz Bednarczyk
CC BY-SA 4.0
2023-10-14T07:14:15.597Z
Did you really mean to put this comment on my answer rather than on the question? Is it specific to Petri nets?
Emil Jeřábek
CC BY-SA 4.0
2023-10-14T16:11:33.753Z
Yes. And their modifications. Plus it also contain other things, but VASSes are canonical problems there.
Bartosz Bednarczyk
CC BY-SA 4.0
2023-10-16T13:33:01.167Z
@EmilJeřábek thanks for adding this in! In fact, I had been thinking of that as well but feared that I would misquote the results.
Hermann Gruber
CC BY-SA 4.0
2023-10-13T20:05:23.267Z
2023-10-13T20:05:23.267Z
Emil Jeřábek
<p>Since the OP also asked for a natural nonelementary problem, here is one.</p>
<p>Let us refer to regular expressions (in the sense of Kleene) that are extended with a complementation operator as <em>extended</em> regular expressions. Let <span class="math-container">$\mathbf{tow}(k,\ell)$</span> denote the <em>tower function</em>, defined as <span class="math-container">$\mathbf{tow}(0,\ell)= \ell$</span> and <span class="math-container">$\mathbf{tow}(k+1,\ell) =2^{\mathbf{tow}(k,\ell)}$</span>.</p>
<p>For extended regular expressions whose nesting depth of complements is bounded by <span class="math-container">$k$</span>, the decision problem whether the complement of the described language is nonempty is in <span class="math-container">$\mathbf{NSPACE}(\mathbf{tow}(k, 2\cdot n))$</span>. On the other hand, there is <span class="math-container">$c&gt;0$</span> such that the problem is not in <span class="math-container">$\mathbf{NSPACE}(\mathbf{tow}(k, c\cdot n))$</span>.</p>
<p>Thus the problem is not elementary for extended regular expressions (i.e. when the nesting depth is not bounded by a constant). According to Holzer/Kutrib (2010), this is proved in L. Stockmeyer's PhD thesis (1974).</p>
<p>Markus Holzer, Martin Kutrib:
<a href="https://doi.org/10.1007/978-3-642-14455-4_3" rel="nofollow noreferrer">The Complexity of Regular(-Like) Expressions.</a> Developments in Language Theory 2010: 16-30</p>
<p>And here comes a natural problem in formal language theory that is decidable but not primitive recursive.</p>
<p>Recall the definition of leftist grammars (<a href="https://en.wikipedia.org/wiki/Leftist_grammar" rel="nofollow noreferrer">Wikipedia</a>), whose definition is motivated by access control systems in computer security.</p>
<blockquote>
<p>A <em>leftist grammar</em> is a formal grammar on which certain restrictions
are made on the left and right sides of the grammar's productions.
Only two types of productions are allowed, namely those of the form
<span class="math-container">$a\to ba$</span> (insertion rules) and <span class="math-container">$cd\to d$</span> (deletion rules). Here,
a,b,c and d are terminal symbols.</p>
</blockquote>
<p>It is not trivial to see that the membership problem for this type of grammars is decidable. This has been shown in Motwani et al. (2000), the work that introduced this type of grammar.</p>
<p>Rajeev Motwani, Rina Panigrahy, Vijay A. Saraswat, Suresh Venkatasubramanian:
<a href="https://doi.org/10.1145/335305.335341" rel="nofollow noreferrer">On the decidability of accessibility problems (extended abstract).</a> STOC 2000: 306-315</p>
<p>Although the types of languages that can be generated by such grammars is severely restricted (we cannot generate all regular languages)... quite surprisingly (to me), the membership problem for leftist grammars is not primitive recursive (Jurdziński 2008).</p>
<p>Tomasz Jurdziński: <a href="https://doi.org/10.1007/978-3-540-70583-3_5" rel="nofollow noreferrer">Leftist Grammars Are Non-primitive Recursive.</a> ICALP (2) 2008: 51-62</p>

CC BY-SA 4.0
2023-10-12T19:19:48.213Z
2023-10-12T19:25:49.077Z
2023-10-12T19:25:49.077Z
Hermann Gruber
<p>Let me give a few examples in the form of decision procedures for natural first-order theories.</p>
<p>By a result of Berman [1], Presburger arithmetic <span class="math-container">$\mathrm{Th}(\mathbb N,+)$</span> (or <span class="math-container">$\mathrm{Th}(\mathbb Z,+,&lt;)$</span>) is complete for the class <span class="math-container">$\mathrm{TimeAlternations}(2^{2^{O(n)}},O(n))$</span>, which is (likely) larger than EEXP, but it is included in, say, EEXPSPACE, or EEEXP.</p>
<p>Further examples like this can be found in Ferrante and Rackoff [2] (predating Berman’s precise characterization): the theory of finite abelian groups, or Skolem arithmetic <span class="math-container">$\mathrm{Th}(\mathbb N,\cdot)$</span> (whose complexity is even one exponential higher than Presburger arithmetic).</p>
<p>Concerning theories with nonelementary complexity, [2] also prove that any consistent theory that has a definable pairing function has complexity at least <span class="math-container">$2^1_{\Omega(n)}$</span>, where <span class="math-container">$\left.\vcenter{\textstyle2^x_n=2^{2^{\cdot^{\cdot^{\cdot^{2^x}}}}}}\right\}n\atop$</span> denotes the iterated exponential. While typical theories with pairing, such as Peano arithmetic, are undecidable, there are some decidable examples: Tenney [5] shows the decidability of <span class="math-container">$\mathrm{Th}(\mathbb N,p)$</span> for many pairing functions <span class="math-container">$p$</span>, including “locally free” pairing functions (this was proved earlier by Mal’cev), the Cantor function <span class="math-container">$\binom{n+m+1}2+n$</span> (reproved later by Cégielski and Richard), and other functions such as <span class="math-container">$2^n(2m+1)$</span> or <span class="math-container">$\max\{n^2,m^2+n\}+m$</span>. Presburger arithmetic with exponentiation <span class="math-container">$\mathrm{Th}(\mathbb N,+,2^x)$</span>, which has a definable pairing function <span class="math-container">$2^n+2^{n+m}$</span>, is decidable by Semenov [4]. Unfortunately, these results do not indicate the computational complexity of the decision procedures, though I believe at least Tenney’s methods should probably yield an upper bound <span class="math-container">$2^1_{O(n)}$</span> matching the Ferrante and Rackoff lower bound. But for a definite example: I proved in [3] that <span class="math-container">$\mathrm{Th}(H_k,\in)$</span>, where <span class="math-container">$H_k$</span> denotes the collection of all sets hereditarily of size at most <span class="math-container">$k$</span> (which has the Kuratowski pairing function for <span class="math-container">$k\ge2$</span>), is decidable with complexity <span class="math-container">$2^1_{O(n)}$</span>.</p>
<h2>References</h2>
<p>[1] Leonard Berman: <em>Precise bounds for presburger arithmetic and the reals with addition: Preliminary report</em>, Proc. 18th FOCS, IEEE, 1977, pp. 95–99, doi <a href="https://doi.org/10.1109/SFCS.1977.23" rel="nofollow noreferrer">10.1109/SFCS.1977.23</a>.</p>
<p>[2] Jeanne Ferrante and Charles W. Rackoff: <em>The computational complexity of logical theories</em>, Lecture Notes in Mathematics vol. 718, Springer-Verlag, 1979, doi <a href="https://doi.org/10.1007/BFb0062837" rel="nofollow noreferrer">10.1007/BFb0062837</a>.</p>
<p>[3] Emil Jeřábek: <em>The theory of hereditarily bounded sets</em>, Mathematical Logic Quarterly 68 (2022), no. 2, pp. 243--256, doi <a href="https://doi.org/10.1002/malq.202100020" rel="nofollow noreferrer">10.1002/malq.202100020</a>. <a href="https://arxiv.org/abs/2104.06932" rel="nofollow noreferrer">arXiv</a></p>
<p>[4] Aleksei L. Semenov: <em>Logical theories of one-place functions on the set of natural numbers</em>, Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya 47 (1983), no. 3, pp. 623–658 (in Russian), English translation in: Mathematics of the USSR, Izvestiya 22 (1984), no. 3, pp. 587–618. doi <a href="https://doi.org/10.1070/IM1984v022n03ABEH001456" rel="nofollow noreferrer">10.1070/IM1984v022n03ABEH001456</a></p>
<p>[5] Richard L. Tenney: <em>Decidable pairing functions</em>, Ph.D. thesis, Cornell University, 1972, <a href="https://hdl.handle.net/1813/5991" rel="nofollow noreferrer">https://hdl.handle.net/1813/5991</a>.</p>

CC BY-SA 4.0
2023-10-08T03:07:01.080Z
Wow, nice upper bounds! Thanks for including them.
Corbin
CC BY-SA 4.0
2023-10-07T07:08:45.733Z
2023-10-13T09:16:23.947Z
2023-10-13T09:16:23.947Z
Emil Jeřábek
<p>I haven't really seen any examples of problems in complexity classes higher then <strong>EEXP</strong>. What are some examples of some primitive recursive problems outside of <strong>EEXP</strong>? Ideally with a large number of Es, for example, problems in <strong>NEEEEXP</strong>. While are here - what are some examples of natural problems that are not in <strong>ELEMENTARY</strong>, and ones that are not in <strong>PR</strong>? So far the only real problems I have seen in those classes are either trivial or ones constructed specifically to be in that class.</p>

CC BY-SA 4.0
2023-10-07T08:19:12.580Z
Could you please clarify what is EEXP? Is EExp the same as 2ExpTime?
Bartosz Bednarczyk
CC BY-SA 4.0
2023-10-07T22:31:58.827Z
@Bartosz Bednarczyk
Yes
Colonizor48
<complexity><exp-time-algorithms>
What are some examples of decidable Natural Problems outside of EEXP?
Colonizor48
# What are some examples of decidable Natural Problems outside of EEXP?

(Asked by: username_0 on 2023-10-06)

I haven't really seen any examples of problems in complexity classes higher then **EEXP**. What are some examples of some primitive recursive problems outside of **EEXP**? Ideally with a large number of Es, for example, problems in **NEEEEXP**. While are here - what are some examples of natural problems that are not in **ELEMENTARY**, and ones that are not in **PR**? So far the only real problems I have seen in those classes are either trivial or ones constructed specifically to be in that class.

**Tags:** complexity, exp-time-algorithms
> **Comments:**
> **username_1**: Could you please clarify what is EEXP? Is EExp the same as 2ExpTime?  
> **username_0**: @Bartosz Bednarczyk Yes  

---

## 3 answers

### Answer by username_2 on 2023-10-07. Score: 12 | Accepted answer

Let me give a few examples in the form of decision procedures for natural first-order theories.

By a result of Berman [1], Presburger arithmetic $\mathrm{Th}(\mathbb N,+)$ (or $\mathrm{Th}(\mathbb Z,+,<)$) is complete for the class $\mathrm{TimeAlternations}(2^{2^{O(n)}},O(n))$, which is (likely) larger than EEXP, but it is included in, say, EEXPSPACE, or EEEXP.

Further examples like this can be found in Ferrante and Rackoff [2] (predating Berman’s precise characterization): the theory of finite abelian groups, or Skolem arithmetic $\mathrm{Th}(\mathbb N,\cdot)$ (whose complexity is even one exponential higher than Presburger arithmetic).

Concerning theories with nonelementary complexity, [2] also prove that any consistent theory that has a definable pairing function has complexity at least $2^1\_{\Omega(n)}$, where $\left.\vcenter{\textstyle2^x\_n=2^{2^{\cdot^{\cdot^{\cdot^{2^x}}}}}}\right\}n\atop$ denotes the iterated exponential. While typical theories with pairing, such as Peano arithmetic, are undecidable, there are some decidable examples: Tenney [5] shows the decidability of $\mathrm{Th}(\mathbb N,p)$ for many pairing functions $p$, including “locally free” pairing functions (this was proved earlier by Mal’cev), the Cantor function $\binom{n+m+1}2+n$ (reproved later by Cégielski and Richard), and other functions such as $2^n(2m+1)$ or $\max\{n^2,m^2+n\}+m$. Presburger arithmetic with exponentiation $\mathrm{Th}(\mathbb N,+,2^x)$, which has a definable pairing function $2^n+2^{n+m}$, is decidable by Semenov [4]. Unfortunately, these results do not indicate the computational complexity of the decision procedures, though I believe at least Tenney’s methods should probably yield an upper bound $2^1\_{O(n)}$ matching the Ferrante and Rackoff lower bound. But for a definite example: I proved in [3] that $\mathrm{Th}(H\_k,\in)$, where $H\_k$ denotes the collection of all sets hereditarily of size at most $k$ (which has the Kuratowski pairing function for $k\ge2$), is decidable with complexity $2^1\_{O(n)}$.

## References

[1] Leonard Berman: *Precise bounds for presburger arithmetic and the reals with addition: Preliminary report*, Proc. 18th FOCS, IEEE, 1977, pp. 95–99, doi [10.1109/SFCS.1977.23](https://doi.org/10.1109/SFCS.1977.23).

[2] Jeanne Ferrante and Charles W. Rackoff: *The computational complexity of logical theories*, Lecture Notes in Mathematics vol. 718, Springer-Verlag, 1979, doi [10.1007/BFb0062837](https://doi.org/10.1007/BFb0062837).

[3] Emil Jeřábek: *The theory of hereditarily bounded sets*, Mathematical Logic Quarterly 68 (2022), no. 2, pp. 243--256, doi [10.1002/malq.202100020](https://doi.org/10.1002/malq.202100020). [arXiv](https://arxiv.org/abs/2104.06932)

[4] Aleksei L. Semenov: *Logical theories of one-place functions on the set of natural numbers*, Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya 47 (1983), no. 3, pp. 623–658 (in Russian), English translation in: Mathematics of the USSR, Izvestiya 22 (1984), no. 3, pp. 587–618. doi [10.1070/IM1984v022n03ABEH001456](https://doi.org/10.1070/IM1984v022n03ABEH001456)

[5] Richard L. Tenney: *Decidable pairing functions*, Ph.D. thesis, Cornell University, 1972, <https://hdl.handle.net/1813/5991>.

> **Comments:**
> **username_4**: Wow, nice upper bounds! Thanks for including them.  

---

### Answer by username_2 on 2023-10-13. Score: 5

The Petri nets/Vector Addition Systems reachability problem is not primitive recursive; more precisely, it is complete for the class $\mathcal F\_\omega$ of the fast-growing hierarchy (essentially the complexity of the Ackermann function). This was shown recently by [Leroux](https://arxiv.org/abs/2104.12695) and [Czerwiński and Orlikowski](https://arxiv.org/abs/2104.13866), settling a problem that has been open for decades.

> **Comments:**
> **username_1**: Not strictly related to the topic but a good reference for problems beyond elementary is the survey by Sylvain Schmitz (https://dl.acm.org/doi/10.1145/2858784)  
> **username_2**: Did you really mean to put this comment on my answer rather than on the question? Is it specific to Petri nets?  
> **username_1**: Yes. And their modifications. Plus it also contain other things, but VASSes are canonical problems there.  
> **username_3**: @EmilJeřábek thanks for adding this in! In fact, I had been thinking of that as well but feared that I would misquote the results.  

---

### Answer by username_3 on 2023-10-12. Score: 3

Since the OP also asked for a natural nonelementary problem, here is one.

Let us refer to regular expressions (in the sense of Kleene) that are extended with a complementation operator as *extended* regular expressions. Let $\mathbf{tow}(k,\ell)$ denote the *tower function*, defined as $\mathbf{tow}(0,\ell)= \ell$ and $\mathbf{tow}(k+1,\ell) =2^{\mathbf{tow}(k,\ell)}$.

For extended regular expressions whose nesting depth of complements is bounded by $k$, the decision problem whether the complement of the described language is nonempty is in $\mathbf{NSPACE}(\mathbf{tow}(k, 2\cdot n))$. On the other hand, there is $c>0$ such that the problem is not in $\mathbf{NSPACE}(\mathbf{tow}(k, c\cdot n))$.

Thus the problem is not elementary for extended regular expressions (i.e. when the nesting depth is not bounded by a constant). According to Holzer/Kutrib (2010), this is proved in L. Stockmeyer's PhD thesis (1974).

Markus Holzer, Martin Kutrib:
[The Complexity of Regular(-Like) Expressions.](https://doi.org/10.1007/978-3-642-14455-4_3) Developments in Language Theory 2010: 16-30

And here comes a natural problem in formal language theory that is decidable but not primitive recursive.

Recall the definition of leftist grammars ([Wikipedia](https://en.wikipedia.org/wiki/Leftist_grammar)), whose definition is motivated by access control systems in computer security.

> A *leftist grammar* is a formal grammar on which certain restrictions
> are made on the left and right sides of the grammar's productions.
> Only two types of productions are allowed, namely those of the form
> $a\to ba$ (insertion rules) and $cd\to d$ (deletion rules). Here,
> a,b,c and d are terminal symbols.

It is not trivial to see that the membership problem for this type of grammars is decidable. This has been shown in Motwani et al. (2000), the work that introduced this type of grammar.

Rajeev Motwani, Rina Panigrahy, Vijay A. Saraswat, Suresh Venkatasubramanian:
[On the decidability of accessibility problems (extended abstract).](https://doi.org/10.1145/335305.335341) STOC 2000: 306-315

Although the types of languages that can be generated by such grammars is severely restricted (we cannot generate all regular languages)... quite surprisingly (to me), the membership problem for leftist grammars is not primitive recursive (Jurdziński 2008).

Tomasz Jurdziński: [Leftist Grammars Are Non-primitive Recursive.](https://doi.org/10.1007/978-3-540-70583-3_5) ICALP (2) 2008: 51-62


---

