Complexity of input output selection

Input output selection is the procedure of choosing a set of inputs (actuators) and outputs (sensors) for a plant from a larger set. The goal is to be able to design a controller that fulfills the specifications for the closed loop. The input output selection problem is shown to fall in the class of problems that are $\cal N\cal P$-hard. However, an algorithm is presented that solves the problem efficiently, under the conditions that (1) the selection criterion satisfies some assumptions, (2) computing the criterion is an involved task, and (3) the number of items to choose from is not too large. The time needed is of the order of the product of the number of items to choose from, the size of the complete solution, and the time spend to evaluate the selection criterion for a single set. An engineering application shows the algorithm to be able to compute a solution in an acceptable time, so it has practical relevance.