P≠NP假设下NP-NPC-P中自然问题的一个候选者(英文)

1975年 ,L ander证明在 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并且在更强但合理的假设下它的确属于

关于图同构复杂性的分析

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。

基于图灵模型的P=?NP问题分析

P=?NP问题是计算复杂性中的核心问题。2000年,美国克雷实验室将其收录为"千禧年大奖"七个问题之首。本文基于图灵模型,对P=?NP问题的研究现状、P=NP/P≠NP证明方法、NPC问题求解方法及研究进展进行阐述。

谈谈P和NP问题

对“21世纪的数学问题”之一的“P=NP7”问题作了论述。

数学家货郎问题的计算复杂性研究

货郎问题(TSP)是研究计算复杂性理论的经典问题.在货郎问题的基础上,提出"数学家货郎问题"(MTSP).经过研究发现,数学家货郎问题是一个典型的NP类问题,但它却不属于P类问题.因此,数学家货郎问题是一个NP类问题与P类问题不相等的例证.