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