UP的相对完全性

[He 88]在第三部分“UP有图灵完全语言吗”?的标题下构造了一个递归Oracle A,并且证明UP^A 无图灵完全语言。本文构造了一个NP Oracle B 并且证明UP^B 有多项式完全语言(从而也就有图灵完全语言)。

一致与非一致复杂类的模型论性质

自从1965年J.Edmonds和A.Cobham提出P-NP问题以来已有30年的研究历史。目前环绕这个问题的大量学术论文和研究专著已使它发展成为计算机科学中最新和最活跃的研究领域之一,近年来,人们除了对由各种类型的图灵机确定的复杂类(如P,NP,PSPACE等)进行研究外,对一些用其他方法定义的非一致复杂类(如P/poly,P/log,NP/poly等)也越来越有兴趣。

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

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