4
$\begingroup$

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.

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

$\endgroup$
  • $\begingroup$ The title and the body of your question ask two different things. What's in the body is trivial: PSPACE is in NEXP. $\endgroup$ – Sasho Nikolov Nov 6 '17 at 4:29
  • $\begingroup$ Verry sorry!! I changed my question. $\endgroup$ – Atsu Nov 6 '17 at 4:33
  • 2
    $\begingroup$ Since PSPACE $\subseteq$ EXP, would't that imply NEXP=EXP(=PSPACE) and thus point #4 applies? $\endgroup$ – Clement C. Nov 6 '17 at 5:22
  • $\begingroup$ You mean first-order theory of the natural numbers with addition, rather than for the reals. $\endgroup$ – Kristoffer Arnsfelt Hansen Nov 6 '17 at 10:38
  • 3
    $\begingroup$ It is still not very clear what you are asking. $\endgroup$ – Kristoffer Arnsfelt Hansen Nov 6 '17 at 10:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.