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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.