4
$\begingroup$

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?

$\endgroup$
9
  • 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$
    – Lamine
    Sep 20, 2023 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$ Sep 21, 2023 at 2:03
  • 2
    $\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$ Sep 21, 2023 at 19:36
  • $\begingroup$ @Hermann Gruber Does SUBEXP being outside PSPACE imply that SETH is false? $\endgroup$ Sep 21, 2023 at 19:45
  • 1
    $\begingroup$ No. I don't see how this could imply anything about the truthiness of (S)ETH... $\endgroup$ Sep 21, 2023 at 21:03

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

Your Answer

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

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