The NP-hardness of the optimal decentralized control (ODC) problem is reflected in the properties of its feasible set. We study the complexity of the ODC problem through an analysis of the set of stabilizing static decentralized controllers and show that there is no polynomial upper bound on its number of connected components. In particular, it is proved that this number is exponential in the order of the system for a class of problems. Since every point in each of these components is the unique solution of the ODC problem for some quadratic objective functional, the results of this work imply that, without prior knowledge for initialization, local search algorithms cannot solve the ODC problem to global optimality for all decentralized control structures. In an effort to understand the connection between the geometric properties of the feasible set of the ODC problem and the control structure, we further identify decentralized structures that admit tractable connectivity properties, using a combination of the Routh-Hurwitz criterion and Lyapunov stability theory.