13
$\begingroup$

What is the complexity of the following problem?

Given an NFA $A$ and a number $k\in \mathbb{N}$ in binary encoding, does there exist a DFA $B$ with at most $k$ states such that $L(A)=L(B)$?

Specifically, is it known whether this is PSPACE-complete or EXPTIME-complete?

This is the decision version of NFA to DFA minimization, but the size bound is given in binary. It's well known that if $k$ is given in unary, the problem is PSPACE-complete (by e.g., reduction from NFA universality).

The problem is clearly in EXPTIME: we can determinize $A$ to obtain an equivalent DFA of exponential size, and then minimize it. However, this method cannot be brought down to PSPACE, since the minimal output may indeed be of exponential size.

My intuition says this should be EXPTIME-complete, but I did not see any research on that.

$\endgroup$
5
  • 2
    $\begingroup$ Intriguing ! It's very surprising that this natural problem does not even seem to be mentioned anywhere. I'm also guessing EXPTIME-complete with no clue on how to prove it, for what it's worth ;) $\endgroup$
    – Denis
    Oct 17, 2021 at 12:58
  • $\begingroup$ Do you know the complexity if you don't even minimize the powerset construction ? Ie you ask if the reachable part of the powerset automaton has size at most k. $\endgroup$
    – Denis
    Oct 17, 2021 at 13:01
  • 2
    $\begingroup$ @Denis - I don't. Does that sound like an easier problem to you? I'm not sure it is, because it restricts you to look at the powerset construction, rather than e.g. giving some condition on the number of Myhill-Nerode classes. But anyway - no idea on either problem. I thought maybe a reduction from the emptiness of an intersection of deterministic tree automata would work, but I haven't given it much thought. $\endgroup$
    – Shaull
    Oct 17, 2021 at 13:17
  • $\begingroup$ I agree it's not clear which is simpler. Indeed some candidates for a reduction are tree automata intersection, P-complete problems on succinct graphs, or directly Turing machines. At the beginning I also thought that my paper "Computing the width of nondeterministic automata" could help because it looks related: it shows EXPTIME-completeness of the width problem: given A and k in unary, is A^k (the product of k copies of A, accepting whenever one of them accept) determinizable by pruning ? Unfortunately, the NFA in the reduction always accepts all words, so it cannot be used for your problem. $\endgroup$
    – Denis
    Oct 17, 2021 at 13:30
  • $\begingroup$ Yeah, I had a look at your paper when I looked around for answers to this. I agree it looks close. $\endgroup$
    – Shaull
    Oct 17, 2021 at 13:41

1 Answer 1

5
$\begingroup$

The problem is in PSPACE, hence is PSPACE-complete.

DFA minimization is in NL; see Theorem 2.1 of [S. Cho and D.T. Huynh. The Parallel Complexity of Finite-State Automata Problems. Information and Computation, 97, 1-22 (1992)]

NL is contained in polyL (deterministic polylogarithmic space).

The subset construction can be implemented by a PSPACE transducer, i.e., a Turing machine whose work tape is PSPACE-bounded. Its output (on an extra tape) will be exponential in general.

By composing the PSPACE transducer with the polyL-machine in the standard space-efficient way (involving the (re-)computation of any bit the polyL-machine requires), we (even) get a PSPACE transducer that given an NFA computes a minimal equivalent DFA.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks! I wasn't aware of this paper. Also, did you open a cs.se account just to answer my question? I'm flattered! :) $\endgroup$
    – Shaull
    Nov 9, 2021 at 7:45
  • 3
    $\begingroup$ Badges and privileges rolling in, so no regrets ;-) $\endgroup$ Nov 9, 2021 at 8:06
  • 2
    $\begingroup$ Thanks Stefan :) It also answers the variant about the powerset, which is in PSPACE as well. $\endgroup$
    – Denis
    Nov 9, 2021 at 13:11
  • $\begingroup$ Stellar answer! I have been well aware of that paper but was unable to connect the dots $\endgroup$ Nov 12, 2021 at 12:44

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.