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:

  • 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
    Commented Jun 10, 2017 at 18:38


Your Answer

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