用结构性质分开复杂类

SEPARATING COMPLEXITY CLASSES BY THEIR STRUCTURAL PROPERTIES

摘要: ＮＰ（或Ｃｏ－ＮＰ）是否包含在Ｐ／ｐｏｌｙ中的问题迄今仍为开问题．８０年代初证明了如果ＮＰＰ／ｐｏｌｙ，则ＰＨ＝Σ２．最近，又有了如果ＮＰＰ／ｐｏｌｙ，则ＰＨ＝ＺＰＰ的证明．文中将借助于广义一阶逻辑Ｌ（τ）及其上的模型论以证明存在ＮＰ（或Ｃｏ－ＮＰ）中的语言，它们没有多项式大小的线路．

Abstract: Whether NP （or Co NP）P/poly is still an open problem. In the early 1980’s, it has been proved that if NPP/poly then PH= Σ 2 . Recently, it has been proved that if NPP/poly then PH=ZPP. In the paper here, it is proved by means of the extended first order logic L（τ） and model theory on it that there are some languages in NP（or Co NP） which do not have polynomial circuits.