计算复杂性理论部分进展简述

• 作者: 朱洪 葛启 蔡进一
• 来源期刊: 中国计算机学会通讯
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: 封面报道
• 页码范围: 27-37,53
• 页数: 12页
• 语种: 中文

摘要

前言 计算复杂性理论博大精深,是计算机科学领域核心之一.复杂性理论和算法的不同之处在于,它不是单单研究解决某个问题的方法,而是研究一类问题的性质.在上世纪60年代中期,哈特马尼斯(Hartmanis)等人提出了通过对资源(时间、空间)需求的不同来划分问题,从此开创了计算复杂性理论.此后几年,大量复杂性类被提出,并且很多新方法被应用,计算复杂性的框架被建立起来.但是随着研究的深入,越来越多的问题也涌现出来,比如说经典的问题P=NP1,是计算复杂性中的核心问题.随着新的问题以及新模型的提出,计算复杂性理论被不断地丰富,并且每一次重大成果的出现都必然伴随着新方法的使用.