We show that the problems to find the smallest acyclic DFA and OBDD with a fixed order of variables that are consistent with given sets of positive and negative examples are not approximable in polynomial time within worst case factors n1/28 and n1/21, respectively, with the input size n unless P = NP.
- Combinatorial problems
- Computational complexity
- Data structures
- Finite state machine minimization