SEPARATING COMPLEXITY CLASSES BY THEIR STRUCTURAL PROPERTIES

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.