$\mathsf{PSPACE}$ membership in exponentially many steps?

Question

I am trying to argue that a certain problem is in $\mathsf{PSPACE}$ and my question is, essentially, whether it is ok to have an algorithm that takes an exponential number of steps as long as, overall, the whole thing stays in polynomial space.

The context for this is that I have a naive algorithm which, it seems to me, shows $\mathsf{PSPACE}$ membership, but I am not entirely certain of the logic behind it.

I can be more concrete. Say we have a set $M$ and a transitive binary relation $>$ on $M$. $M$ is exponentially large (think all possible assignments), and $>$ can be partial and have cycles. If $a>b$, for $a,b\in M$, then we say that $a$ dominates $b$. If $a$ dominates every element in $M$ (including itself), we say that $a$ is dominating.

I know that, given $>$ and some $a\in M$, determining whether $a$ is dominating in $>$ is $\mathsf{PSPACE}$-complete. Call this the $\mathsf{DOMINATING}$ problem, and we can take it as a given that it is $\mathsf{PSPACE}$ complete.

The problem I am faced with is now is what we could call the $\exists\mathsf{DOMINATING}$ problem: given $>$, determine whether there exists a dominating element in $>$.

My naive algorithm for $\exists\mathsf{DOMINATING}$ is as follows: take every element in $M$, ask whether it is dominating in $>$, and stop if one is found. This, it seems to me, is in $\mathsf{PSPACE}$: even though we might have to go through an exponential number of $\mathsf{PSPACE}$ queries, we stay in polynomial space throughout.

Answer 1

whether it is ok to have an algorithm that takes an exponential number of steps as long as, overall, the whole thing stays in polynomial space.

Yes, of course. Polynomial space means exactly what it says.

The only reason you should worry is if you think that your algorithm takes more time than $2^{n^c}$ for all $c$. In that case, it must either use more than polynomial space or loop forever since, there are only $|\Sigma|^{n^k}$ configurations of a tape of length $n^c$ using alphabet $\Sigma$, only $n^k$ possible head positions and only a constant number of possible states. That means there are only $|Q|n^k|\Sigma|^{n^k} \leq 2^{n^c}$ (for large enough $c$) possible configurations for a polynomial space Turing machine so if it runs for more than that many steps, it must have seen the same configuration twice so it must be in an infinite loop.