# Can you determinize an NFA in PSPACE?

QUESTION

Given some NFA $$A$$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $$PSPACE$$?

MORE DETAILS

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 $$ 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$$.

MY ATTEMPTS

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).

Thank you.

• As I understand it, you are talking about keeping track of the current set of states the NFA could be in. That can be computed for each step in space bounded by the number of states and time bounded by the number of transitions in the NFA. – vonbrand Aug 12 at 14:15

Determinization can exponentially increase the number of states: the language of $$0$$$$1$$strings such that the $$k$$th-from-last character is $$0$$ can be recognized by an NFA with something like $$k+1$$ states, but any DFA for that language has at least $$2^k$$ states.