摘要
自从1965年J.Edmonds和A.Cobham提出P-NP问题以来已有30年的研究历史。目前环绕这个问题的大量学术论文和研究专著已使它发展成为计算机科学中最新和最活跃的研究领域之一,近年来,人们除了对由各种类型的图灵机确定的复杂类(如P,NP,PSPACE等)进行研究外,对一些用其他方法定义的非一致复杂类(如P/poly,P/log,NP/poly等)也越来越有兴趣。
出处
《自然杂志》
1995年第5期300-300,共1页
Chinese Journal of Nature
基金
863高科技(863-306-05-07-5)
南航大基金(S9498-802)资助项目
关键词
非一致复杂类
P-NP问题
一致复杂类
模型论
<Keyword>computation complexty，uniform and nonuniform complexity classes，Boolcan circuits，P-NP problem
