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

摘要

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