Optimizing TRIEs for ordered pattern matching is Π2 P-complete

We consider the complexity of constructing a data structure, called TRIEs, with the minimum operational cost for the ordered pattern matching problem, a problem abstracting the essence of executing Prolog problems; a TRIE with minimal cost corresponds to a program with the minimum worst case operational cost. Based on the recent non-approximability results developed by Arora et al. (1992) and Condon et al. (1993), we show that to approximate the optimum cost of this problem to within some constant ratio is Π₂^P-hard. The result implies that the problem of Prolog program optimization is probably as hard