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.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ 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) $\endgroup$– LamineSep 20 at 22:30
-
1$\begingroup$ @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. $\endgroup$– Colonizor48Sep 21 at 2:03
-
1$\begingroup$ @Lamine If SUBEXP contains problems outside PSPACE (which we currently cannot rule out I suppose), then SETH doesn't imply anything about those. $\endgroup$– Hermann GruberSep 21 at 19:36
-
$\begingroup$ @Hermann Gruber Does SUBEXP being outside PSPACE imply that SETH is false? $\endgroup$– Colonizor48Sep 21 at 19:45
-
1$\begingroup$ No. I don't see how this could imply anything about the truthiness of (S)ETH... $\endgroup$– Hermann GruberSep 21 at 21:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
