用结构性质分开复杂类

• 作者: 吕义忠
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 结构复杂性 广义一阶逻辑 图论
• 年，卷（期）: 1999,（8）
• 所属期刊栏目: 计算机理论与技术
• 页码范围: 932-935
• 分类号: TP301.5
• 语种: 中文

摘要

NP(或Co-NP)是否包含在P/poly中的问题迄今仍为开问题. 80年代初证明了如果NP(∩)P/poly,则PH=Σ2.最近,又有了如果NPP/poly,则PH=ZPP的证明.文中将借助于广义一阶逻辑(L)(τ)及其上的模型论以证明存在NP(或Co-NP)中的语言,它们没有多项式大小的线路.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吕义忠	南京航空航天大学计算机科学与工程系	3	1	1.0	1.0