1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Try finding an NPSPACE algorithm for your problem. By Savitch's theorem. PSPACE=NPSPACE. $\endgroup$ – Yuval Filmus Jun 28 '18 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 Jun 28 '18 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$ – Yuval Filmus Jun 28 '18 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 Jun 28 '18 at 17:25
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.