# Determine the number of reachable states in a subset construction?

Is there a polynomial time algorithm to determine the number of reachable states in the subset construction of a NFA to a DFA without having to construct the entire DFA?

## 1 Answer

Start with a 3SAT instance $$\phi$$ on $$n$$ variables with $$m$$ clauses $$C_1,\ldots,C_m$$. For each clause $$C_j$$, we construct an NFA $$A_j$$ which reads a binary input string, interpreting its first $$n$$ symbols as encoding a truth assignment, and checks whether the clause is satisfied. If $$C_j$$ is satisfied, then on the $$(n+1)$$'th symbol it branches to $$n$$ new states.

Now consider an NFA consisting of the NFAs $$A_1,\ldots,A_m$$ together with an initial state with $$\epsilon$$-transitions to the starting states of $$A_1,\ldots,A_m$$ (alternatively, if you allow multiple initial states, you can just put all of them together). If $$\phi$$ is satisfiable then the number of reachable states in the corresponding DFA will be at least $$n^m$$, otherwise it will be at most $$n^{m-1} + 2^m n + 1$$.