о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



ýṹʷֿ

ժҪNP(Co-NP)ǷP/polyеΪ. 80֤NPP/polyPH=2.NPP/polyPH=ZPP֤.нڹһ߼ϵģ֤NP(Co-NP)еԣûжʽС·.
ؼʡṹԣһ߼ͼ
ͼšTP301.5
SEPARATING COMPLEXITY CLASSES BY THEIR STRUCTURAL PROPERTIES
L Yi-Zhong
(Department of Computer Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016)
(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093)
AbstractWhether NP (or Co-NP)P/poly is still an open problem. In the early 1980's, it has been proved that if NPP/poly then PH=2. Recently, it has been proved that if NPP/poly then PH=ZPP. In the paper here, it is proved by means of the extended first-order logic  and model theory on it that there are some languages in NP(or Co-NP) which do not have polynomial circuits.
Key wordsstructural complexity, extended first-order logic, graph theory
1
һ¼ģܷжNPȫԵδõ14.1980KarpLipton2ԼPippenger5ݵ˻ڶʽн纯ķһ¸P/poly֤ǡʽС·ĸͬ.ͬʱKarp,LiptonSipser֤NPP/polyPH=226.ǰKblerWatanabe֤һԿɹԼжʽС·ZPP(ӶNP)PH=13.Ļ˼򵥿ͼƽܵ¸Խһ̽NP(Co-NP)P/poly֮Ĺϵҽڹһ߼ϵģۣ֤NP(Co-NP)д޶ʽС·.
2
ĸ={0,1}Ϊ(Ϊˡ)ڵĦϵһļϣNΪȫļϣ˫䣬ʹκδҽ.ˣеĴɰNؼΪ.
Ƕ򵥿ͼG=V,eУ㼯V̶Ϊ߹ϵeΪVϵһԳƵĶԪϵ78.裬ɶGĵյͼҼΪ.ǳΪGnı(e(i,j)Ϊֵ01Լg(1)=)ֳgΪGı뺯.ȻͬһͼegӦȷĹϵùһԱ£G=V,egΪGı뺯ҽ(ʵΪ(*))߼BIT(x,y)=yĵxλֵ910.
ʹ÷һ¸P/poly,䶨ΪУpolyΪʽн纯ڶʽp,ʹöκȻn,|f(n)|p(n)14.
3·ͱƽ
GΪ򵥿ͼ(ԺΪͼ)gΪGı뺯{Cm}m1ΪʽС·أ14ݣ¶壺
1. kNʹöκnN{Cm}m1ܡk,g(n)˵G{Cm}m1ƽ.
2. CΪͼļ.κͼGУGCҽG{Cm}m1ƽܣ˵C{Cm}m1ƽ.
1. κμA*AжʽС·ҽAP/poly1245.
2. CΪͼGļϣgΪGı뺯CʽС·ƽܵҽڶʽʱνhͶʽн纯fʹöκͼGУGCҽ
֤. (Ҫ)CʽС·{Cm}m1ƽܣ{Cm}m1ܵļΪA1AP/polyʰ壬ڶʽʱνh(PмB)Ͷʽн纯fʹöκͼG

()ɼеhfܾһP/polyеļA䲢1ãAرĳʽС·{Cm}m1.ˣɼãƽ.2C{Cm}m1ƽ.
֤.
4ýṹʷֿ
WatanabeáһԼ·աһṹʷֿ˸NPDEXT.ákȫͼһṹNP(Co-NP)P/polyķֿ.
1. S={G|GΪͼҴrʹGȫͼKr}SκζʽС·ƽ.
֤. (֤)SʽС·{Cm}m1ƽܣ2ڶʽνhͶʽн纯fʹöκͼG

Ȼڷ֤ļ£hfǹ̶ģͬԺx,y󳤶Ⱥ|x|Ҳǹ̶.Immermanģʱ̶νʺͺһ(BITs,,o,max)ʹǱе߼νʺ߼9.ۿģͣͬɽ̶h,f,x,y|x|.ǿɼʽ(1)Ϊ

УAΪһеһ׹ʽ.
ͬأ̶BITD(x)(x-1)H(x)(x/2)ͼӷ+Уǰ(*)ɼΪ
gΪGı뺯
УBΪϵһ׹ʽ.
Ȼ

ڣֱʽ(2)(3)(4)ұߵһ׾Ϊеķ߼ŽΪegͦ={e,g}910.
ϵľӵΪ

ʧһԣ覣һӼΪ

ֻҪͼGΪȫͼKmͿɵͼĩGȷeg佫,,12m.֮.ˣɽԶæпģu(ע⣺ǿ)7.ȻԿɽuΪ.ڿɵ3ۣ
(1) uеĹϵeͺgӦ֣gΪӦeͼı뺯.
(2) uӦףʴrʹeӦͼвrȫͼKr.
(3) uӦ12meӦͼӦ.Ȼ(2)(3)ìܣ֤ǵĶ.
֤.
2. T={r,g|rΪgΪͼKrͼı뺯}.
֤. (֤)TP/polyڶʽνhͶʽн纯fʹã

ڣڶ1еS

ڣ2SʽС·ƽܣ붨1ìܣ֤.
֤.
3. Co-NPеļϽжʽС·.
֤. ֪2еTCo-NP146.TжʽС·1TP/poly붨2ìܣ֤.
֤.
4. NPеļϽжʽС·.
֤. ΪԲգʣNPм޶ʽС·.
֤.
ĿõȻѧ(Ŀ6983003)Ŀ
߼飺ңУ1937ڣҪ߼㸴Էо
ߵλҡϾպѧѧ빤ϵϾ210016
Ͼѧ¼صʵҡϾ210093)
ο
1Balcazar J L, Diaz J, Gabarro J. Structural Complexity. Heidelberg: Springer-Verlag, 1988(I), 1990(II)
2Karp R, Lipton R. Some connections between non-uniform and uniform complexity classes. In: Proc of 12th ACM Symp on Theory of Computing. Heidelberg: Springer-Verlag, 1980. 302309
3Kbler J, Watanabe O. New collapse consequences of NP having small circuits. Lecture Notes in Computer Science #944. New York: Springer-Verlag, 1995, 196207
4L Yizhong, Sun Huicheng. The Principle of Structural Complexity. Nanjing: Nanjing University Press, 1995
5Pippenger N. On simultaneous resource bounds. In: Proc 20th IEEE Symp Foundations of Computer Science. Heidelberg: Springer-Verlag, 1979. 307311
6Sipser M. A complexity theoretic approach to randomness. In: Proc 15th Ann ACM Symp on Theory of Computing. Heidelberg: Springer-Verlag, 1983. 330335
7Bondy J A, Murty U S R. Graph Theory with Applications. Amsterdam: North-Holland, 1976
8Wilson R J. Introduction to Graph Theory, Third Edition, New York: Longman Inc, 1985
9Immerman N, Descriptive and computational complexity. In: Hartmanis J ed. Computational Complexity Theory, Proc of Symposia in Applied Mathematics, Vol 38. Georgia: American Mathematical Society, 1989. 7591
10Malitz J. Introduction to Mathematical Logic. Heidelberg: Springer-Verlag, 1979
յڣ1997-11-21
ĸڣ1998-09-07
