K-L问题的解决

复杂性研究中的一个重点问题是非一致复杂类的测度问题.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吗?"     

关于NP完全问题的多项式线路可判定性

在计算复杂性领域里，大多数复杂类都是按照接受它们的图灵机而加以描述的。８０年代初，人们广泛关注被多项式大小的线路可判定的集合类并且得到了许多有趣的结果。但是，迄今是否ＮＰ完全问题是多项式大小的线路可判定的问题仍然是开的。最好的结果是，如果答案是肯定的，则多项式时间的分层便塌方到２级，即，ＰＨ＝Σ２。本文考虑一个特殊的无穷图的集合和讨论它被多项式大小线路逼近接受的问题，且利用紧致性定理和常数扩张法证明了存在集合Ａ∈ＣＯ－ＮＰ＼Ｐ／ｐｏｌｙ。     

关于Fleury算法的一点注记

为了使用Ｆｌｅｕｒｙ的算法，在每一步都必须去判断图Ｇ－ｅ的连通性［１］。本文将给出一个十分简单的判断图的连通性的线性算法。为了证明它的正确性，本文将证明以下三个条件是等价的：（１）图Ｇ是连通的；（２）Ｍ的任意ｎ－１行都是线性无关的（这里Ｍ为图Ｇ的关联矩阵）；（３）在Ｍ中存在ｎ－１个线性无关的行。