Reliable interpretability requires integration of complexity-theoretic and experimental efforts

System opacity underlies many of the risks we currently worry about and undermines many of the intended scientific applications of AI. Understanding the conditions for interpretability methods to meet the requirements of scientific and societal needs is a central concern. In this position paper, we argue that (i) the field of interpretability is at a critical juncture, with a minimal foundation of theoretical and empirical results, and that (ii) to seize the scientific opportunities and meet societal challenges, the field needs \textit{integration of complexity-theoretic and experimental efforts} to guide the discovery of methods with adequate performance and knowledge of the conditions that make it possible. To support the field at this juncture, we introduce a comprehensive, actionable research strategy to complement existing efforts, combining a \textit{computational path} involving modeling and parameterized complexity analysis, and an \textit{algorithmic path} based on heuristic design and parametric experimentation. We illustrate its necessity, potential, and feasibility through real case studies of explainability and inner interpretability.