P≠NP假设下NP-NPC-P中自然问题的一个候选者
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported by the National Natural Science Foundation of China under G rant No.69973013 (国家自然科学基金)


A Candidate for Natural Problems in NP-NPC-P under P≠NP
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    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并且在更强但合理的假设下它的确属于NPI.

    Abstract:

    In 1975, Lander showed that there exist some languages in NP NPC P (denoted as NPI) under the assumption P≠NP. But the language constructed there is indeed an unnatural one because the construction needs to run all polynomial time Turing machines. So far, no natural problems have been proved to be in NPI under P≠NP and finding a natural problem in NP NPC P is indeed an important open problem. In this paper this long open problem is partially solved. A 2+ f(m) HSAT model is defined. Based on this model,a candidate for natural problems in ((NP-NPC)-P),denoted as NPI,under the assumption P≠NP is given,and the authors have proven that it is not in NP-Completer P≠NP.Actually,it indeed is in NPI under some stronger but plausible assumption.In comparison,similar for the two other candidates,GI and Facting,are not known.

    参考文献
    相似文献
    引证文献
引用本文

赵运磊,朱洪. P≠NP假设下NP-NPC-P中自然问题的一个候选者.软件学报,2001,12(5):656-658

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2000-05-22
  • 最后修改日期:2000-10-16
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号