[credulousperson]

A small note: If you allow randomized algorithms, this problem is actually known to be in P^PP^PP^PP which is well within PSPACE in some sense, but still a ridiculously bad bound.

See https://cstheory.stackexchange.com/a/4056.