基于模型论的复杂性问题分析方法研究

摘要：

近年来,模型论的许多思想和方法逐渐渗透、融合到其他的学科,特别是在理论计算机科学中,有着重要的理论及应用价值.该文利用有限模型论的相关理论,对计算复杂性问题、计算复杂性和逻辑学在有限结构上的关系作了分析和研究,主要讨论了对不同复杂类的捕获问题.根据研究的结果,对一些常见复杂性问题的进行了捕获和分析.

关键词：模型论、计算复杂性、复杂类、NP问题

所属期刊栏目：8

分类号：TP311(计算技术、计算机技术)

在线出版日期：2012-08-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：3374-3376