In this paper we study a class of uncertainty model validation=invalidation problems for linear discrete-time systems. We consider models described by a linear fractional transformation (LFT) of modeling uncertainties, which are structured, time invariant or time varying, and are bounded in H β or '1 norms. The experimental data available for use in invalidation are either input-output time series observations or frequency response measurements. We analyze the computational complexity associated with these problems. While earlier work showed that for LFT models with an unstructured uncertainty the invalidation problems can be reduced to one of solving linear matrix inequalities, and hence may be tackled readily using well-developed numerical methods, in this paper we provide a simple proof to show that in the presence of structured uncertainties they are all NP-hard with respect to the number of uncertainty blocks, suggesting that the problems are inherently intractable from a computational standpoint. Additionally, we also demonstrate that the problems do become tractable when the LFT model description is changed to an additive one, leading to LMI-based invalidation tests similar to those obtained elsewhere. These results indicate that the main source of the computational di culty lies in the LFT description together with the structured nature of the uncertainties.