-2
$\begingroup$

Not problems like chess. I'm thinking problems that would be very useful to be able to solve in sub-exponential time. These would be problems not known to be EXPTIME complete.

Edit I mean problems that are not known to be in NP and assuming $NP \neq EXP$, Problems that are thought in EXP but there could hypothetically be a deterministic polynomial time algorithm for

$\endgroup$
3
  • $\begingroup$ If you down-vote please state why. I'm new to this. $\endgroup$ Jan 6 at 20:26
  • $\begingroup$ I didn't downvote, but I wanted to comment on the latest revision. It's probably better to avoid changing the question after getting an answer. It's important to formulate the question precisely from the start so that it incorporates all requirements you had in mind, so you're not adjusting it after you get an answer. If you discover you asked the wrong question, it might be better to post a new question with the question you should have asked. $\endgroup$
    – D.W.
    Jan 6 at 21:49
  • $\begingroup$ Allright. Closing this then. $\endgroup$ Jan 7 at 0:39
2
$\begingroup$

If the Polynomial Hierachy does not collapse then there are incomplete sets between $PH$ and $PSPACE$, see https://cstheory.stackexchange.com/questions/7639/is-there-a-pspace-intermediate-language/7640. These sets would be also incomplete in $EXP$, because $PSPACE \subseteq EXP$

$\endgroup$
1
  • $\begingroup$ Nice! This answers also the updated question. $\endgroup$ Jan 9 at 20:33
3
$\begingroup$

Any $\mathsf{NP}$-complete problem is in $\mathsf{EXPTIME}$ and not known to be $\mathsf{EXPTIME}$-complete, since it is still unknown whether $\mathsf{NP} = \mathsf{EXPTIME}$ or not.

$\endgroup$
3
  • $\begingroup$ Yes but this is somewhat trivial. I meant problems outside of NP(Or PH in general) that are in EXP. $\endgroup$ Jan 6 at 20:01
  • $\begingroup$ No problem is known to be in $\mathsf{EXPTIME}$ and not in $\mathsf{NP}$ so I don't know what you expect… $\endgroup$
    – Nathaniel
    Jan 6 at 20:07
  • $\begingroup$ generalized chess without the 50 move rule is exp-time complete. I'm asking for Problems in exp-time(as far as we know), but not known to be in NP nor known to be EXPTIME complete. These could theoretically have some sort of deterministic polynomial algorithm algorithm but none are known. I should specify that we assume $NP \neq EXP$ $\endgroup$ Jan 6 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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