In the world of formal languages, we have always been interested in the problem of finding the smallest “algorithm” for deciding a given language. Moore’s algorithm for DFA minimization is a standard part of a first course in theory of computing. Jiang and Ravikumar have shown, on the other hand, that NFA minimization is PSPACE-hard.
We will discuss a related problem for the computational model of deterministic decision trees. Let \(f\) be a Boolean function given as either a truth table or as a circuit. In both of these cases, how difficult is it to find the smallest complexity of a decision tree for computing \(f\)? (This is commonly known as the “query complexity” of \(f\)). We will show that this problem is NC\(_1\)-hard and PSPACE-hard, respectively. The second bound is tight, and the first bound is close to being tight.