6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Could you please clarify what is EEXP? Is EExp the same as 2ExpTime? $\endgroup$ Oct 7, 2023 at 8:19
  • $\begingroup$ @Bartosz Bednarczyk Yes $\endgroup$ Oct 7, 2023 at 22:31

3 Answers 3

12
$\begingroup$

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.

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

[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. arXiv

[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

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

$\endgroup$
1
  • $\begingroup$ Wow, nice upper bounds! Thanks for including them. $\endgroup$
    – Corbin
    Oct 8, 2023 at 3:07
5
$\begingroup$

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 and Czerwiński and Orlikowski, settling a problem that has been open for decades.

$\endgroup$
4
  • 1
    $\begingroup$ Not strictly related to the topic but a good reference for problems beyond elementary is the survey by Sylvain Schmitz (dl.acm.org/doi/10.1145/2858784) $\endgroup$ Oct 13, 2023 at 20:31
  • $\begingroup$ Did you really mean to put this comment on my answer rather than on the question? Is it specific to Petri nets? $\endgroup$ Oct 14, 2023 at 7:14
  • $\begingroup$ Yes. And their modifications. Plus it also contain other things, but VASSes are canonical problems there. $\endgroup$ Oct 14, 2023 at 16:11
  • $\begingroup$ @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. $\endgroup$ Oct 16, 2023 at 13:33
3
$\begingroup$

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. 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), 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). 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. ICALP (2) 2008: 51-62

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.