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