Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$?
I'm asking this as I want to be able to construct $\overline A$ (the complement of $A$) in poly-space complexity.
More specifically, I want to receive $\left <A,w \right >$ as input ($A$ is an NFA) and decide if $w \in \overline A$. So I want to construct $\overline A$ and simulate (in poly-space) $\overline A$ on $w$.
I know that determinizing an NFA (using Subset-Construction) can blow up exponentially. But, I thought that the determinization and/or the simulation can happen "on the fly", where each step overrides the previous one.
Other then this thought, I can't manage to develop it into an actual algorithm (if it's at all possible).