<p>SUBEXP is neither known or widely believed to lie in PSPACE (and -- contrary to one of the comments -- this is not known to have any connection to SETH).  It is not known whether the containment &quot;SUBEXP in PSPACE&quot; would imply that SUBEXP is in NP; there are oracles relative to which P=NP and PSPACE = EXP, and thus there are oracles relative to which this implication fails.</p>

CC BY-SA 4.0
2023-09-26T19:36:59.803Z
2023-09-26T19:36:59.803Z
Eric Allender
<p>Let SUBEXP is the complexity class of all problems solvable in sub-exponential time in the length of the input. What are the known properties of this class? Is it known to be contained in PSPACE, if so, is it known to be contained in NP? Is it thought to lie outside of PSPACE? My intuition says there should be problems that are Solvable in at least Sub-expoential time and Sub-exponential space, but not be in PSPACE.</p>
<p>Also, if SUBEXP lies outside of NP, and there is a SUBEXP complete problem, wouldn't that disprove ETH?</p>

CC BY-SA 4.0
2023-09-20T22:30:17.030Z
P is of course strictly contained in SUBEXP,  and we don't know if P=PSPACE. So a positive response to your first question would imply P≠PSPACE. Same thing for the second question (P≠NP). However, if you assume SETH, then SUBEXP is contained in NP (which is contained in - or equal to - PSPACE)
Lamine
CC BY-SA 4.0
2023-09-21T02:03:23.007Z
@Lamine Even assuming SETH, wouldn't there probably exist problems solvable in  Subexponential time and Subexponential(but superpolynomial) Space? Therefore implying that SUBEXP is not contained in PSPACE? This is just institutional but still, at the very least this is an argument against SETH.
Colonizor48
CC BY-SA 4.0
2023-09-21T19:36:49.703Z
@Lamine If SUBEXP contains problems outside PSPACE (which we currently cannot rule out I suppose), then SETH doesn't imply anything about those.
Hermann Gruber
CC BY-SA 4.0
2023-09-21T19:45:16.920Z
@Hermann Gruber Does SUBEXP being outside PSPACE imply that SETH is false?
Colonizor48
CC BY-SA 4.0
2023-09-21T21:03:40.080Z
No. I don't see how this could imply anything about the truthiness of (S)ETH...
Hermann Gruber
CC BY-SA 4.0
2024-03-23T18:20:34.713Z
There is no SUBEXP-complete problem.
Emil Jeřábek
CC BY-SA 4.0
2024-03-23T19:54:11.643Z
(But even if there were, I don’t see how this would imply anything about the truth of ETH.)
Emil Jeřábek
CC BY-SA 4.0
2024-03-24T23:43:09.390Z
@Emil Jerabek, if SUBEXP had complete problems and was outside of PSPACE, that would imply that NP was contained in SUBEXP.
Colonizor48
CC BY-SA 4.0
2024-03-25T06:17:41.750Z
@Colonizor48 No, it would imply no such thing. I have no idea why you think that.
Emil Jeřábek
<time-complexity><np><complexity><pspace>
is SUBEXP contained within PSPACE?, NP?
Colonizor48
# is SUBEXP contained within PSPACE?, NP?

(Asked by: username_0 on 2023-09-20)

Let SUBEXP is the complexity class of all problems solvable in sub-exponential time in the length of the input. What are the known properties of this class? Is it known to be contained in PSPACE, if so, is it known to be contained in NP? Is it thought to lie outside of PSPACE? My intuition says there should be problems that are Solvable in at least Sub-expoential time and Sub-exponential space, but not be in PSPACE.

Also, if SUBEXP lies outside of NP, and there is a SUBEXP complete problem, wouldn't that disprove ETH?

**Tags:** time-complexity, np, complexity, pspace

> **Comments:**
> **username_1**: P is of course strictly contained in SUBEXP,  and we don't know if P=PSPACE. So a positive response to your first question would imply P≠PSPACE. Same thing for the second question (P≠NP). However, if you assume SETH, then SUBEXP is contained in NP (which is contained in - or equal to - PSPACE)  
> **username_0**: @username_1 Even assuming SETH, wouldn't there probably exist problems solvable in  Subexponential time and Subexponential(but superpolynomial) Space? Therefore implying that SUBEXP is not contained in PSPACE? This is just institutional but still, at the very least this is an argument against SETH.  
> **username_2**: @username_1 If SUBEXP contains problems outside PSPACE (which we currently cannot rule out I suppose), then SETH doesn't imply anything about those.  
> **username_0**: @username_2 Does SUBEXP being outside PSPACE imply that SETH is false?  
> **username_2**: No. I don't see how this could imply anything about the truthiness of (S)ETH...  
> **username_3**: There is no SUBEXP-complete problem.  
> **username_3**: (But even if there were, I don’t see how this would imply anything about the truth of ETH.)  
> **username_0**: @Emil Jerabek, if SUBEXP had complete problems and was outside of PSPACE, that would imply that NP was contained in SUBEXP.  
> **username_3**: @username_0 No, it would imply no such thing. I have no idea why you think that.  

---

## 1 answers

### Answer by username_4 on 2023-09-26. Score: 7

SUBEXP is neither known or widely believed to lie in PSPACE (and -- contrary to one of the comments -- this is not known to have any connection to SETH). It is not known whether the containment "SUBEXP in PSPACE" would imply that SUBEXP is in NP; there are oracles relative to which P=NP and PSPACE = EXP, and thus there are oracles relative to which this implication fails.


---

