南京航空航天大学学报（英文版）2000，Vol.17Issue(1)：1-3,3.
K-L问题的解决
THE SOLUTION OF K-L PROBLEM
摘要
Abstract
A central problem in the study of complexity is the measure of nonuniform complexity classes. BPPP/poly has been proved by Aldman, and EXPSPACEP/poly by Kannan. We propose the definition of approximate acceptance with which we discuss the nonuniform complexity of the K sized complete subgraph problem. The method of modal theory is used and the K sized complete subgraph problemP/poly, co-NPP/poly and NPP/poly is proved. This paper solves the Karp-Lipton′s open problem: "NPP/poly?"关键词
计算复杂性/非一致复杂性/模型论/逼近接受/P/polyKey words
computational complexity/nonuniform complexity/model theory/approximate acceptance/P/poly分类
航空航天引用本文复制引用
吕义忠,高晓波..K-L问题的解决[J].南京航空航天大学学报（英文版）,2000,17(1):1-3,3.基金项目
国家自然科学基金(编号:69583003)和南京大学国家重点实验室基金资助项目. （编号:69583003）
