排序方式: 共有3条查询结果,搜索用时 0 毫秒
1
1.
在计算复杂性领域里,大多数复杂类都是按照接受它们的图灵机而加以描述的。80年代初,人们广泛关注被多项式大小的线路可判定的集合类并且得到了许多有趣的结果。但是,迄今是否NP完全问题是多项式大小的线路可判定的问题仍然是开的。最好的结果是,如果答案是肯定的,则多项式时间的分层便塌方到2级,即,PH=Σ2。本文考虑一个特殊的无穷图的集合和讨论它被多项式大小线路逼近接受的问题,且利用紧致性定理和常数扩张法证明了存在集合A∈CO-NP\P/poly。 相似文献
2.
复杂性研究中的一个重点问题是非一致复杂类的测度问题.Aldman已经证明了BPPP/poly,而Kannan证明了EXPSPACEP/poly.本文提出逼近接受的概念,用来讨论K-团问题的非一致复杂性.本文中使用了模型论的方法,证明了K-团问题P/poly,co-NPP/poly和NPP/poly.因此,本文解决了Karp和Lipton(K-L)提出的开问题:"NPP/poly吗?" 相似文献
3.
吕义忠 《南京航空航天大学学报》1998,30(4):470-472
为了使用Fleury的算法,在每一步都必须去判断图G-e的连通性[1]。本文将给出一个十分简单的判断图的连通性的线性算法。为了证明它的正确性,本文将证明以下三个条件是等价的:(1)图G是连通的;(2)M的任意n-1行都是线性无关的(这里M为图G的关联矩阵);(3)在M中存在n-1个线性无关的行。 相似文献
1