摘要:图上的诸多计算问题都是NP难问题, 因此研究中经常尝试将问题限定在一些具有良好结构的特定图类上. 这类研究在过去的几十年间收获了大量自然图类上的高效算法, 其中很大一部分都能统一到算法元定理框架下. 算法元定理是一类通用的结论, 主要研究模型检测问题, 即在特定结构上判定特定逻辑框架下任意公式的满足性. 现有的算法元定理大多借助结构图论工具研究图的性质, 并且考虑参数复杂性意义下的高效性. 在许多良构的图类上, 一些常见逻辑的模型检测问题具有参数复杂性意义下的高效算法, 即是固定参数易解的. 由于不同逻辑的表达能力不同, 对应的模型检测问题的易解范围也有显著的区别, 探索这些易解范围也是算法元定理研究的重要课题. 研究发现, 一阶逻辑模型检测的易解性与图的稀疏性密切关联. 目前学界对于稀疏图类的认识已经较为成熟, 近年的研究重心逐渐转向一些良构的稠密图类, 研究面临着更多的挑战. 研究表明, 在许多复杂的稠密图类上, 模型检测问题仍有可能是易解的. 对易解范围的探索至今仍在继续, 该领域中仍存在大量的未解问题. 本文将全局性地介绍算法元定理的研究, 旨在为国内的相关研究提供一些线索和助力.