<p>The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial).
In the Complexity Zoo, there are four kinds of relationships being mentioned ( <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N" rel="nofollow noreferrer">https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N</a> )</p>

<ol>
<li><p>NEXP vs. Interactive Proof Systems</p>

<blockquote>
  <p>Equals MIP [BFL91] (but not relative to all oracles).
  NEXP is in MIP* [IV12].
  NEXP is in P/poly if and only if NEXP = MA [IKW01].</p>
</blockquote></li>
<li><p>NEXP vs. Randomized Polynomial Time Complexity Classes</p>

<blockquote>
  <p>[KI02] show the following:
  If P = RP, then NEXP is not computable by polynomial-size arithmetic circuits.
  If P = BPP and if checking whether a Boolean circuit computes a function that is close to a low-degree polynomial over a finite field is in P, then </p>
</blockquote></li>
<li><p>NEXP vs. Small Size Nonuniform Circuits </p>

<blockquote>
  <p>NEXP is not in P/poly.
  If NEXP is in P/poly, then matrix permanent is NEXP-complete.
  Does not equal NP [SFM78].
  Does not equal EXP if and only if there is a sparse set in NP that is not in P.</p>
</blockquote></li>
</ol>

<p>Off course, Ryan William's breakthrough separation between NEXP and ACC (and also SYM $\circ$ THR) is contained in this category. </p>

<ol start="4">
<li>NEXP vs. EXP

<blockquote>
  <p>There exists an oracle relative to which EXP = NEXP but still P does not equal NP [Dek76].
  The theory of reals with addition (see EXPSPACE) is hard for NEXP [FR74].</p>
</blockquote></li>
</ol>

<p>One of important complexity resources which is not mentioned above is space complexity, and one of the most natural classes is PSPACE.</p>

<p>My Question is the following and a reference request question:</p>

<blockquote>
  <p>Q1: Is there some <em>known</em> theorems with the assumption that NEXP is in PSPACE? </p>
</blockquote>

<p>My intention of this question is as follows.</p>

<p>As an example, we consider collapses of PH (the polynomial time hierarchy).
By Karp-Lipton's theorem NP $\subset$ P/poly implies PH collapses into the second level.
However, NP $\subseteq$ P implies PH collapses into the first level.
These two claims mean that the claim NP $\subset$ P is <em>more unlikely</em> than NP $\subseteq$ P/poly.  </p>

<p>Similarly, NEXP $\subseteq$ PSPACE is more unlikely than NEXP $\subseteq$ EXP.</p>

<p>So, my question is about some comparison between two unlikely conclusions. </p>

CC BY-SA 3.0
2017-11-06T04:29:44.383Z
The title and the body of your question ask two different things. What's in the body is trivial: PSPACE is in NEXP.
Sasho Nikolov
CC BY-SA 3.0
2017-11-06T04:33:56.363Z
Verry sorry!!
I changed my question.
Atsu
CC BY-SA 3.0
2017-11-06T05:22:04.490Z
Since PSPACE $\subseteq$ EXP, would't that imply NEXP=EXP(=PSPACE) and thus  point #4 applies?
Clement C.
CC BY-SA 3.0
2017-11-06T10:38:13.057Z
You mean first-order theory of the _natural numbers_ with addition, rather than for the reals.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-11-06T10:42:06.923Z
It is still not very clear what you are asking.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-11-09T19:01:48.187Z
For what it's worth, NEXP vs PSPACE is the exponentially-padded version of NP vs L: NP=L then NEXP=PSPACE. (I know this kind of goes the "wrong direction," but it may help with intuition.)
Joshua Grochow
<cc.complexity-theory><reference-request><complexity-classes><time-complexity><space-complexity>
What happens when PSPACE contains NEXP?
Atsu
# What happens when PSPACE contains NEXP?

(Asked by: username_0 on 2017-11-06)

The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial).
In the Complexity Zoo, there are four kinds of relationships being mentioned ( <https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N> )

1. NEXP vs. Interactive Proof Systems

   > Equals MIP [BFL91] (but not relative to all oracles).
   > NEXP is in MIP\* [IV12].
   > NEXP is in P/poly if and only if NEXP = MA [IKW01].
2. NEXP vs. Randomized Polynomial Time Complexity Classes

   > [KI02] show the following:
   > If P = RP, then NEXP is not computable by polynomial-size arithmetic circuits.
   > If P = BPP and if checking whether a Boolean circuit computes a function that is close to a low-degree polynomial over a finite field is in P, then
3. NEXP vs. Small Size Nonuniform Circuits

   > NEXP is not in P/poly.
   > If NEXP is in P/poly, then matrix permanent is NEXP-complete.
   > Does not equal NP [SFM78].
   > Does not equal EXP if and only if there is a sparse set in NP that is not in P.

Off course, Ryan William's breakthrough separation between NEXP and ACC (and also SYM $\circ$ THR) is contained in this category.

4. NEXP vs. EXP
   > There exists an oracle relative to which EXP = NEXP but still P does not equal NP [Dek76].
   > The theory of reals with addition (see EXPSPACE) is hard for NEXP [FR74].

One of important complexity resources which is not mentioned above is space complexity, and one of the most natural classes is PSPACE.

My Question is the following and a reference request question:

> Q1: Is there some *known* theorems with the assumption that NEXP is in PSPACE?

My intention of this question is as follows.

As an example, we consider collapses of PH (the polynomial time hierarchy).
By Karp-Lipton's theorem NP $\subset$ P/poly implies PH collapses into the second level.
However, NP $\subseteq$ P implies PH collapses into the first level.
These two claims mean that the claim NP $\subset$ P is *more unlikely* than NP $\subseteq$ P/poly.

Similarly, NEXP $\subseteq$ PSPACE is more unlikely than NEXP $\subseteq$ EXP.

So, my question is about some comparison between two unlikely conclusions.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, time-complexity, space-complexity
> **Comments:**
> **username_1**: The title and the body of your question ask two different things. What's in the body is trivial: PSPACE is in NEXP.  
> **username_0**: Verry sorry!! I changed my question.  
> **username_2**: Since PSPACE $\subseteq$ EXP, would't that imply NEXP=EXP(=PSPACE) and thus  point #4 applies?  
> **username_3**: You mean first-order theory of the _natural numbers_ with addition, rather than for the reals.  
> **username_3**: It is still not very clear what you are asking.  
> **username_4**: For what it's worth, NEXP vs PSPACE is the exponentially-padded version of NP vs L: NP=L then NEXP=PSPACE. (I know this kind of goes the "wrong direction," but it may help with intuition.)  

---

## 0 answers

