###
DOI:
Journal of Software:2001.12(5):656-658

P≠NP假设下NP-NPC-P中自然问题的一个候选者
赵运磊,朱洪
(复旦大学计算机科学系,上海 200433)
A Candidate for Natural Problems in NP-NPC-P under P≠NP
ZHAO Yun lei,ZHU Hong
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2652   Download 2800
Received:May 22, 2000    Revised:October 16, 2000
> 中文摘要: 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.
中文关键词: NP-Complete  Karp-归约;SAT;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.
keywords: NP complete  Karp reduction  SAT  NPI
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under G rant No.69973013 (国家自然科学基金) Supported by the National Natural Science Foundation of China under G rant No.69973013 (国家自然科学基金)
Foundation items:
Reference text:

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

ZHAO Yun lei,ZHU Hong.A Candidate for Natural Problems in NP-NPC-P under P≠NP.Journal of Software,2001,12(5):656-658