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

On Decidability of NP Complete Problems by Polynomial Sized Circuit

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

In the field of complexity theory, most of complexity classes are described according to their acceptance by different kinds of Turing machines. At the beginning of the decade 80′s, and as a direct consequence of Karp and Lipton, the class of sets which are decidable by polynomial sized circuits has caused wide attention, and a lot of interesting results have been obtained. But up to now, the problem whether NP complete problem is decidable by polynomial sized circuits is still open. The best result concerning it is that if the answer is “yes” then the polynomial time hierarchy collapse to level 2, i.e. PH=Σ 2. A special set of infinite graphs is considered, and the acceptance of this set by polynomial sized circuits is discussed approximately. Using the compactness theorem and the method of constant expansion, it is proved that there is a set A∈CO-NP\P/poly .