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

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 22,2000
  • Revised:October 16,2000
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063