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

Thank you.

  • $\begingroup$ 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. $\endgroup$ – vonbrand Aug 12 '19 at 14:15

The subset construction can be computed (and negated) in polynomial space. Remember that the output doesn't count as part of the space usage in bounded space computation.

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.

So determinizing doesn't give you a polynomial space algorithm to determine if an NFA accepts its input. But you can simulate all computation paths of the NFA simultaneously: as you read the input, just keep track of the set of states the automaton could be in, and see if that set includes an accepting state once you've read the whole input.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.