P≠NP假设下NP—NPC—P中自然问题的一个候选者

来源 :软件学报 | 被引量 : 0次 | 上传用户：lixiaoliangtony

【摘要】

：

1975年,Lander证明在P≠NP假设下存在一个语言属于NP-NPC-P(NPI).但Lander给出语言并不是一个自然的语言因在该语言的构造中需运行所有多项式时间的图灵机.迄今为止,还没有自

【作者】

：

赵运磊朱洪

【机构】

：

复旦大学计算机科学系

【出处】

：

软件学报

【发表日期】

：

2001年5期

【关键词】

：

NP-COMPLETE Karp-归约 SAT NP-NPC-P 计算机自然问题 NPcomplete Karpreduction SAT NPI

【基金项目】

：

国家自然科学基金

下载到本地 , 更方便阅读

下载此文赞助VIP

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

论文部分内容阅读

1975年,Lander证明在P≠NP假设下存在一个语言属于NP-NPC-P(NPI).但Lander给出语言并不是一个自然的语言因在该语言的构造中需运行所有多项式时间的图灵机.迄今为止,还没有自然的语言被证明在P≠NP假设下属于NPI,并且在P≠NP假设下寻找一个属于NPI的自然语言是一个重要的未解决问题.作者部分解决了此长期未解决的问题.定义了2+f(m)-HAST模型.基于该模型，给出了在P≠NP假设下NP-NPC-P中自然问题的一个候选者.已证明在P≠NP 假设下它不属于NPC并且在更强但合理的假

其他文献

基于生态协同的多目标优化研究

在分析现有多目标优化技术的基础上,提出了一种基于生态协同的多目标优化算法.此算法借鉴生态学中的生态种群密度竞争方程来描述多目标间的复杂关系,可以同时从个体和种群层

期刊

多目标优化非劣解遗传算法生态协同生态种群密度竞争方程EcologyFunctionsGenetic algorithmsMathematical

关于几种植物治疗肝病的药效探讨

肝炎是一种病毒性传染病,在我国人群中的传播面积极为广泛,危害性极大.治疗肝病特别是乙肝,仍是人类一大难题.本人通过20多年的亲身试验及近100名患者的治疗,研究出几种植物(

期刊

植物治疗药效肝炎乙肝肝硬化甲肝中药免疫疗法

基于云的概念划分及其在关联采掘上的应用

将数量型属性转换为布尔型属性是数量型属性关联规则采掘的主要方法,但如何使区间的划分合理一直是研究的热点.传统的划分方法由于不能反映数据间的实际分布规律或者是划分的

期刊

关联规则云模型云变换数据采掘数据库概念划分AlgorithmsBoundary conditionsData structuresDataba

基于特征线条的手势识别

单目视觉的手势识别系统,通常把人手建模成一个像素或者一块,从整体上分析手势的运动参数并提取表观特征.从细微之处着手,融合颜色、运动和边缘等多种信息以提取能够反应人手结构特性的特征线条,并将特征线条分割成小的曲线段,跟踪这些曲线段的运动.采用平面模型对手势图像表观的变化建模,根据各个曲线段的运动,融合成手的整体运动分量.同时分析了图像坐标系的选取和对运动参数的影响,提出了随手运动的坐标系,以抽取平移

期刊

特征线条平面模型手势识别图像处理计算机视觉characteristic curve planar model translation-indepe

用于函授教学的计算机辅助复习方式

本文通过对函授学习特点的分析,及参加函授学习的学生所遇到的问题特点的分析,提出了一种用于函授教学的计算机辅助复习方式,这种方式能帮助学生制定适合他自己需要的复习方

期刊

函授教学计算机辅助复习复习方式复习方案复习效果复习阶段

化学新课程理念下教师在问题解决教学中的作用

本文依据新课程理念,从如何精心设计化学问题,营造和谐的课堂气氛,创设良好的质疑氛围及指导学生学会解决问题等方面阐述了教师的作用.

期刊

化学教学问题解决教学新课程理念课堂气氛化学问题质疑氛围中学师范教育

P≠NP假设下NP—NPC—P中自然问题的一个候选者

其他学术论文