<p>The problem is in PSPACE, hence is PSPACE-complete.</p>
<p>DFA minimization is in NL; see Theorem 2.1 of <a href="https://www.sciencedirect.com/science/article/pii/089054019290002W" rel="noreferrer">[S. Cho and D.T. Huynh. The Parallel Complexity of Finite-State Automata Problems. Information and Computation, 97, 1-22 (1992)]</a></p>
<p>NL is contained in polyL (deterministic polylogarithmic space).</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-11-09T07:45:52.100Z
Thanks! I wasn't aware of this paper. Also, did you open a cs.se account just to answer my question? I'm flattered! :)
Shaull
CC BY-SA 4.0
2021-11-09T08:06:01.883Z
Badges and privileges rolling in, so no regrets ;-)
Stefan Kiefer
CC BY-SA 4.0
2021-11-09T13:11:23.747Z
Thanks Stefan :) It also answers the variant about the powerset, which is in PSPACE as well.
Denis
CC BY-SA 4.0
2021-11-12T12:44:15.387Z
Stellar answer! I have been well aware of that paper but was unable to connect the dots
Hermann Gruber
CC BY-SA 4.0
2021-11-08T21:11:29.027Z
2021-11-08T21:11:29.027Z
Stefan Kiefer
<p>What is the complexity of the following problem?</p>
<blockquote>
<p>Given an NFA <span class="math-container">$A$</span> and a number <span class="math-container">$k\in \mathbb{N}$</span> in binary encoding, does there exist a DFA <span class="math-container">$B$</span> with at most <span class="math-container">$k$</span> states such that <span class="math-container">$L(A)=L(B)$</span>?</p>
</blockquote>
<p>Specifically, is it known whether this is PSPACE-complete or EXPTIME-complete?</p>
<p>This is the decision version of NFA to DFA minimization, but the size bound is given in binary.
It's well known that if <span class="math-container">$k$</span> is given in unary, the problem is PSPACE-complete (by e.g., reduction from NFA universality).</p>
<p>The problem is clearly in EXPTIME: we can determinize <span class="math-container">$A$</span> 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.</p>
<p>My intuition says this should be EXPTIME-complete, but I did not see any research on that.</p>

CC BY-SA 4.0
2021-10-17T12:58:43.327Z
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 ;)
Denis
CC BY-SA 4.0
2021-10-17T13:01:26.727Z
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.
Denis
CC BY-SA 4.0
2021-10-17T13:17:13.330Z
@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.
Shaull
CC BY-SA 4.0
2021-10-17T13:30:22.833Z
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.
Denis
CC BY-SA 4.0
2021-10-17T13:41:27.477Z
Yeah, I had a look at your paper when I looked around for answers to this. I agree it looks close.
Shaull
<automata-theory><minimization>
Complexity of NFA to DFA minimization with binary threshold
Shaull
# Complexity of NFA to DFA minimization with binary threshold

(Asked by: username_0 on 2021-10-17)

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.

**Tags:** automata-theory, minimization
> **Comments:**
> **username_1**: 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 ;)  
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: Yeah, I had a look at your paper when I looked around for answers to this. I agree it looks close.  

---

## 1 answers

### Answer by username_2 on 2021-11-08. Score: 5 | Accepted answer

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)]](https://www.sciencedirect.com/science/article/pii/089054019290002W)

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.

> **Comments:**
> **username_0**: Thanks! I wasn't aware of this paper. Also, did you open a cs.se account just to answer my question? I'm flattered! :)  
> **username_2**: Badges and privileges rolling in, so no regrets ;-)  
> **username_1**: Thanks Stefan :) It also answers the variant about the powerset, which is in PSPACE as well.  
> **username_3**: Stellar answer! I have been well aware of that paper but was unable to connect the dots  

---

