摘要
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?”
复杂性研究中的一个重点问题是非一致复杂类的测度问题。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吗 ?”
基金
国家自然科学基金!(编号 :695 83 0 0 3 )
南京大学国家重点实验室基金资助项目&&
