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