K-L问题的解决(英文)

• 作 者: 吕义忠 高晓波
• 机 构: 南京航空航天大学计算机科学与工程系!南京210016
• 出 处: 南京航空航天大学学报：英文版
• 发表日期: 2000年1期
• 关键词: 计算复杂性 非一致复杂性 模型论 逼近接受 P/pol computational complexity nonuniform complexity model
• 基金项目: 国家自然科学基金!(编号 :695 83 0 0 3 ),南京大学国家重点实验室基金资助项目&&

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