6
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 9
    $\begingroup$ 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 en.wikipedia.org/wiki/ELEMENTARY $\endgroup$
    – Mateus de Oliveira Oliveira
    Dec 9, 2012 at 13:31
  • $\begingroup$ @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. $\endgroup$
    – Chris Pressey
    Dec 9, 2012 at 16:11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Huck Bennett
    Dec 9, 2012 at 16:40
  • 2
    $\begingroup$ @MateusdeOliveiraOliveira maybe you can make this an answer ? $\endgroup$
    – Suresh Venkat
    Dec 9, 2012 at 17:21
  • $\begingroup$ @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. $\endgroup$
    – Chris Pressey
    Dec 10, 2012 at 12:21

1 Answer 1

Reset to default
13
$\begingroup$

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}$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Chris Pressey
    Dec 10, 2012 at 13:10

Your Answer

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

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