6

For the longest time I was under the impression that PR contains NEXP. Try as I might, I am unable to recall where I picked up this notion. I've looked recently, but I have not been able to find anything about what is known about their relationship.

All that I can currently conclude about them is that it's almost certainly not the case that PR = NEXP, as there are known NEXP-complete problems, while the notion of completeness for PR is problematic.

What is known about the relationship between PR and NEXP?

Community
  • 1
Chris Pressey
  • 380
  • 2
  • 7
  • 9
    I think NEXP is strictly contained in PR. I might be missing something but, $ELEMENTARY = DTIME(2^n)\cup DTIME(2^{2^n}) \cup DTIME(2^{2^{2^n}}) \cup ...$. It is known that ELEMENTARY is strictly contained in PR. And $NEXP\subseteq ELEMENTARY$. Thus NEXP is strictly contained in PR. See http://en.wikipedia.org/wiki/ELEMENTARY – Mateus de Oliveira Oliveira Dec 09 '12 at 13:31
  • @Mateus, do you have a reference or proof for $NEXP\subseteq ELEMENTARY$? The wikipedia article you link to doesn't seem to claim that -- it only claims $EXP\subsetneq ELEMENTARY$. Perhaps it is possible to easily derive the former from the latter, but I'm not confident enough of my understanding of $NEXP$ to say. – Chris Pressey Dec 09 '12 at 16:11
  • 1
    @Chris: In general $NTIME(f(n)) \subseteq DTIME(2^{f(n)})$, so $NEXP = NTIME(2^{poly(n)}) \subseteq DTIME(2^{2^{2^n}}) \subsetneq ELEMENTARY$ as Mateus said. – Huck Bennett Dec 09 '12 at 16:40
  • 2
    @MateusdeOliveiraOliveira maybe you can make this an answer ? – Suresh Venkat Dec 09 '12 at 17:21
  • @Huck: could I trouble you for a reference or proof sketch of that NTIME-DTIME relationship? That does sound familiar (Papadimitriou's book?) but I may be confusing it with Savitch's Theorem. I thought such a basic relationship would be mentioned in the zoo, but doesn't seem to be. Also, this 2009 blog post calls it (or something very close to it) a conjecture. – Chris Pressey Dec 10 '12 at 12:21
  • @ChrisPressey The straightforward relationship is $NTIME(f(n)) \subseteq DTIME(2^{O(f(n))})$ whenever $f(n) = \Omega(n)$ by, say, executing a BFS on the possible computation tree of the corresponding NTM which contains $O(k^{t(n)}) = 2^{O(t(n))}$ nodes for $k$ smaller than the finite cardinality of the transition function defining the NTM. HuckBennett's bound is rather loose, but sufficient. I believe this is one of the first examples in the time complexity section in Sipser's book. The conjecture in the blog post requires the coefficient of $t(n)$ in the exponent to be arbitrarily small. – Yonatan N Dec 11 '12 at 06:57
  • Thanks @Yonatan, I got it now. I think "in general" is what threw me. It works when $f$ has some substance to it, the open question is how small $f$ can be. – Chris Pressey Dec 11 '12 at 10:16
  • Yes, Yonatan is right, I should have $NTIME(f(n)) \subseteq DTIME(f(n) \cdot 2^{f(n)})$. Then $f(n) = \Omega(n) \Rightarrow NTIME(f(n)) \subseteq 2^{O(f(n))}$. The conclusion is the same. – Huck Bennett Dec 12 '12 at 14:50

1 Answers1

13

Transforming the comments above into an answer:

NEXP is strictly contained in PR. Indeed define the class ELEMENTARY as $$\mathsf{ELEMENTARY}=\text{DTIME}(2^n)\cup \text{DTIME}(2^{2^n}) \cup \text{DTIME}(2^{2^{2n}}) \cup ...$$

It can be shown that ELEMENTARY is strictly contained in PR. Since $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$ we have that $\mathsf{NEXP}$ is strictly contained in $PR$.

As pointed out by Huck Bennett above, the fact that $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$ is a consequence from the fact that

$$\mathsf{NEXP} = \text{NTIME}(2^{\text{poly}(n)}) \subseteq \text{DTIME}(2^{2^{2^n}}) \subsetneq \mathsf{ELEMENTARY}$$

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Mateus de Oliveira Oliveira
  • 3,052
  • 21
  • 27
  • Thank you kindly. I'm still a little fuzzy on Huck Bennett's assertion, but I've convinced myself that the specific relationship $\text{NTIME}(2^{\text{poly}(n)}) \subseteq \text{DTIME}(2^{2^{2^n}})$ holds. – Chris Pressey Dec 10 '12 at 13:10