K-L问题的解决

来源 :南京航空航天大学学报（英文版） | 被引量 : 0次 | 上传用户：Zoeyha

【摘要】

：

复杂性研究中的一个重点问题是非一致复杂类的测度问题.Aldman已经证明了BPPP/poly,而Kannan证明了EXPSPACEP/poly.本文提出逼近接受的概念,用来讨论K-团问题的非一致复

【作者】

：

吕义忠高晓波

【机构】

：

南京航空航天大学计算机科学与工程系,南京,210016

【出处】

：

南京航空航天大学学报（英文版）

【发表日期】

：

2000年1期

【关键词】

：

计算复杂性非一致复杂性模型论逼近接受 P/poly

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

复杂性研究中的一个重点问题是非一致复杂类的测度问题.Aldman已经证明了BPPP/poly,而Kannan证明了EXPSPACEP/poly.本文提出逼近接受的概念,用来讨论K-团问题的非一致复杂性.本文中使用了模型论的方法,证明了K-团问题P/poly,co-NPP/poly和NPP/poly.因此,本文解决了Karp和Lipton(K-L)提出的开问题:“NPP/poly吗?”

其他文献

用“创新智慧”激发新活力

该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥

期刊

立足煤海勇担当不断创新奋超越

期刊

“闪光”的王班长

期刊

浮生若梦

请下载后查看，本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.

期刊

浅谈品牌LOGO中的信息图形设计

科技进步使得生活中充满无处不在的信息。随着信息量的增加,获取信息的受众出现了对各种信息是否需要摄取的困惑,而信息图形设计以其易识、易读、易记得特点,逐渐成为图形设

期刊

LOGO设计过程信息内容公司理念热门研究企业知名度信息传递科技进步形象设计调查数据

高职教师教育信仰研究——以河北省石家庄市5所高职院校为例

随着国家对职业教育重视程度和改革力度的不断加大，社会对高职教师的要求也在不断提高。高职教师作为高职教育发展的中坚力量，不仅担负着传授专业知识技能的责任，更担负着育人的

学位

高等职业院校教师管理教育信仰构成要素

大雁二矿250综采工作面CO来源的分析及治理

通过实验室试验及现场观测证明,大雁二矿250综采工作面回风道中CO长期超限的原因,是由于该工作面所开采的30#煤层在常温条件下氧化的结果。CO来源的确定为该矿的安全生产及CO

期刊

煤炭氧化CO来源治理

“神耳”听出“牛氏维修经”

期刊

体校青少年运动员英语学习动机研究

体校青少年运动员是一个特殊的学生群体。由于英语基础薄弱，加上训练后身体的疲惫等原因，青少年运动员更容易放弃英语学习。了解他们的英语学习动机，并引导他们树立正确的英语学

学位

体校英语教学青少年运动员英语学习动机学习兴趣自我效能感

让每颗“小棋子”动起来——河北兴泰发电公司安全生产长周期侧记

期刊

K-L问题的解决

与本文相关的学术论文