The problem is taken out of Theory of Computational Complexity:

enter image description here

Now, I think I've successfully proven that $ALL_{NFA} = \{(A) : A$ is an NFA and $ L(A) = \Sigma^*\} \leq_p MIN_{NFA}$. Which implies that $MIN_{NFA}$ is PSPACE hard, as the latter is itself.

However I'm stuck proving this problem is in PSPACE - I've thought of defining a nondeterministic Turing Machine, that takes an NFA and a natural number $n$ as input, and on each branch of the computation creates a NFA with number of states less than or equal to $n$. This machine will go on to compare the resulting NFA (in each branch) to the given one (this problem is itself in PSPACE, but I've yet to prove it myself).

However it seems to me the above idea may use more than poly. time, as we may have to keep track of the transition function of each NFA; whose image is in the power set of its states.

Any assistance?

  • $\begingroup$ Try finding an NPSPACE algorithm for your problem. By Savitch's theorem. PSPACE=NPSPACE. $\endgroup$ Commented Jun 28, 2018 at 14:06
  • $\begingroup$ @YuvalFilmus hey, that's what I tried to describe above; and I tried to describe why I think my solution may fail. Can you address that? Or give me an idea for such algo please? $\endgroup$
    – Mariah
    Commented Jun 28, 2018 at 15:07
  • 1
    $\begingroup$ (1) How is $n$ encoded? (2) How long is the encoding of an NFA with $n$ states over a fixed alphabet? $\endgroup$ Commented Jun 28, 2018 at 15:10
  • $\begingroup$ @YuvalFilmus so for (1) i guess $n$ is encoded in binary. for (2), an encoding of an NFA has to be in length poly. in the number of states times the given alphabet; but this is what I don't understand, the transition function end up in $P(Q)$, and there are $2^{|Q|}$ such options, and don't we need to keep track of all these options in space? $\endgroup$
    – Mariah
    Commented Jun 28, 2018 at 17:25

1 Answer 1


For a fixed alphabet, you can describe an NFA with $n$ states using $O(n^2)$ bits. Now, given a DFA $M$ and an integer $n$ (encoded in binary), we consider two cases:

  1. $M$ has at most $n$ states. In this case, there exists an NFA for $L(M)$ having at most $n$ states.

  2. $M$ has more than $n$ states. In this case, the input length is $\Omega(n)$ bits, and so we can guess an NFA with $n$ states in polynomial space.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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