许多机器学习、认知/脑科学和社会领域中提出的神经网络应用都依赖于通过电路发现实现内在可解释性的可行性。这需要对可行的算法选项进行实证和理论探索。尽管在启发式算法的设计和测试方面取得了进展，但人们仍然担心其在可扩展性和忠实性方面的局限性，尤其是在我们缺乏对它们所部署的解决问题的复杂性特性的理解的情况下。为了解决这个问题，我们利用经典和参数化计算复杂性理论研究电路发现：(1) 我们描述了一个概念性框架，用于根据描述、解释、预测和控制的可能性来推理电路查找查询；(2) 我们正式化了一套全面的查询，这些查询捕捉了机制解释，并提出了一个用于分析它们的正式框架；(3) 我们利用它来确定许多查询变体和实际感兴趣的多层感知器（例如，变压器的一部分）的复杂性。我们的发现揭示了一个具有挑战性的复杂性景观。许多查询是难以处理的（NP-hard，$\Sigma^p_2$-hard），在约束模型/电路特征（例如，深度）时仍然是固定参数难以处理的（W[1]-hard），并且在加法、乘法和概率近似方案下是不可近似的。为了应对这种复杂性，我们证明存在一些转换可以利用更好的理解的启发式算法来解决这些难题（NP- vs. $\Sigma^p_2$-complete），并证明更简单的查询的可处理性（PTIME）或固定参数可处理性（FPT），这些查询保留了有用的可能性。这个框架使我们能够理解可解释性查询的范围和局限性，探索可行的选项，并比较现有和未来架构之间资源需求。