Problems that are known to be PSPACE-hard, lie within EXPTIME, and resist proof of EXPTIME-completeness are relatively rare, but several combinatorial games and some non-game problems fall into this category. Below are key examples, with a focus on well-studied problems:

1. Go (with Chinese or Japanese rules)

• Complexity Status: PSPACE-hard (proven by Lichtenstein and Sipser [1]...

Short answer

Among “natural” problems, there aren’t many robust examples that are provably PSPACE-hard, lie in EXPTIME, and for which EXPTIME-hardness is still open. In fact, for most well-studied two-player perfect-information finite games, the winner problem ends up either PSPACE-complete (when the length of play is polynomially bounded) or EXPTIME-complete (when exponentially long plays are po...

The inclusion PSPACE ⊆ EXPTIME is strict only if PSPACE ≠ EXPTIME, so any problem that is • at least as hard as every problem in PSPACE (PSPACE-hard) and
• solvable in deterministic exponential time (in EXPTIME)

is a candidate for lying strictly between the two classes. During the last thirty-five years a number of such problems have been identified – almost all of them are two–player perfect-...

Below is a small catalogue of “natural’’ decision problems whose complexity is known to lie strictly between

 PSPACE-hard and EXPTIME  (PSPACE ⊆ ? ⊆ EXPTIME)

but for which neither an EXPTIME–hardness proof nor a membership–in–PSPACE proof is known.
All upper bounds are obtained in the routine way: on an input of size n we can explore the (at most) exponentially-large game tree in deter...

Excellent question. This touches on a fascinating and less-traversed corner of complexity theory compared to the P vs. NP landscape. The search for "intermediate" problems between PSPACE and EXPTIME is indeed a hunt for problems that have resisted classification for decades.

The core of the issue, especially for the game-theoretic problems you mentioned, often boils down to a single, hard-to-answ...

<think> We are looking for problems that are known to be PSPACE-hard and in EXPTIME, but not known to be complete for either PSPACE or EXPTIME (or any class in between). The problem should resist classification as complete for one of these classes.

The question mentions that lifted (succinct) versions of problems between LOGSPACE and PTIME are accepted, but problems that are not of this form are ...

Here is a small “grab‐bag” of natural decision problems that are known to be PSPACE‐hard, lie in EXPTIME (indeed the trivial EXPTIME‐upper bound comes from the fact that you can always do a brute‐force search through all game‐trees or all configurations in time 2^{poly(n)}), yet despite decades of work nobody has managed to show they are either PSPACE‐complete or EXPTIME‐complete.

1. Phutball
   ...

Intermediate Problems Between PSPACE and EXPTIME

You're asking about problems that are known to be PSPACE-hard and in EXPTIME, but not known to be complete for either class - essentially the potential "intermediate" problems that might exist in the gap between PSPACE and EXPTIME (assuming PSPACE ≠ EXPTIME).

Game-Related Problems

As you've noted, many of these problems come from the analysi...

This is an interesting question about the complexity landscape between PSPACE and EXPTIME. Let me provide a comprehensive answer about known intermediate problems.

Known Problems Between PSPACE and EXPTIME

Game-Based Problems

1. Phutball (Philosopher's Football)
   • As you mentioned, this is PSPACE-hard and in EXPTIME
   • The game involves moving a ball on a grid by creating and ju...