K-L问题的解决

• 作者: 吕义忠 高晓波
• 来源期刊: 南京航空航天大学学报（英文版）
• 学科: 航空航天
• 关键词: 计算复杂性 非一致复杂性 模型论 逼近接受 P/poly
• 年，卷（期）: 2000,（1）
• 所属期刊栏目: 理论与试验研究
• 页码范围: 1-3
• 页数: 3页
• 分类号: V2
• 字数: 744字
• 语种: 英文
• DOI: 10.3969/j.issn.1005-1120.2000.01.001

摘要

复杂性研究中的一个重点问题是非一致复杂类的测度问题.Aldman已经证明了BPPP/poly,而Kannan证明了EXPSPACEP/poly.本文提出逼近接受的概念,用来讨论K-团问题的非一致复杂性.本文中使用了模型论的方法,证明了K-团问题P/poly,co-NPP/poly和NPP/poly.因此,本文解决了Karp和Lipton(K-L)提出的开问题:"NPP/poly吗?"

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吕义忠	南京航空航天大学计算机科学与工程系	3	1	1.0	1.0
2	高晓波	南京航空航天大学计算机科学与工程系	1	1	1.0	1.0