16
$\begingroup$

Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves.

Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, and resisting all efforts to be proved complete for one of these classes ?

Lifted (succinct) versions of problems between LOGSPACE and PTIME are accepted, but even more interesting would be problems that are not of this form.

Here are some I found, this area of complexity theory seems to be the realm of games:

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ I think the more correct way of stating the question is asking for candidate problems in ExpTime - PSpace - ExpTime-hard. Note that e.g. in the case of P vs. NP we don't know if Factoring or GI is P-hard. $\endgroup$ – Kaveh Jun 10 '17 at 18:38

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.