计算机科学 ›› 2020, Vol. 47 ›› Issue (7): 8-20.doi: 10.11896/jsjkx.191200176
姜新文
JIANG Xin-wen
摘要: NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的问题。如果NP=P,对于很多困扰科学研究的困难计算问题,理论上就存在多项式时间算法来迅速求解它们。而现代密码学建立在NP≠P的假设之上。人们希望存在难解问题,希望基于难解问题构造加密算法,希望能够利用难解问题的求解复杂性对抗分析和攻击。如果NP=P,所有在NP≠P假定之上开展的计算研究都至少需要重新审视其意义。NP完全问题的求解复杂性决定NP=P是否成立。针对一个被称为MSP问题的新问题,文中提出了一个关于MSP问题的多项式时间算法,并给出了该算法的证明和时间复杂性分析。由于已经发表了十多个经典的NP完全问题到MSP问题的归结以及MSP问题到SAT问题的归结,因此MSP问题存在多项式时间算法这样一个研究结果对于研究NP=P有重要和积极的意义。
中图分类号:
[1]THE CLAY MATHEMATICS INSTITUTE.P vs.NP Problem [EB/OL].https://www.claymath.org/millennium-problems/p-vs-np-problem. [2]SCIENCE (AAAS).125 Questions of Science [EB/OL].http://www.sciencemag.org/site/feature/misc/webfeat/125th/. [3]FORTNOW L.The status of the P versus NP problem[J].Communications of the ACM,2009,52(9):78-86. [4]COOK S.The importance of the P versus NP question[J].Journal of the ACM (JACM),2003,50(1):27-29. [5]THE CLAY MATHEMATICS INSTITUTE.Millennium Problems [EB/OL].https://www.claymath.org/millennium-problems/. [6]KAYAL N.The complexity of the annihilating polynomial[C]//2009 24th Annual IEEE Conference on Computational Comple-xity.IEEE,2009:184-193. [7]DEOLALIKAR V.P≠NP [EB/OL].https://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf. [8]VARDI M Y.on P,nP,and computational complexity[J].Communications of the ACM,2010,53(11):5. [9]AGRAWAL M,KAYAL N,SAXENA N.PRIMES is in P[J].Annals of mathematics,2004,160(2):781-793. [10]VALIANT L G.Quantum circuits that can be simulated classically in polynomial time[J].SIAM Journal on Computing,2002,31(4):1229-1254. [11]KNUTH D.All questions answered[J].Notices of the AMS,2002,49(3):318-324. [12]GASARCH W I.The p=?np poll[J].Sigact News,2002,33(2):34-47. [13]GAREY M R,JOHNSON D S.Computers and intractability:A guide to the theory of NP-completeness [M].San Francisco: freeman,1979. [14]JIANG X W.Determining the H Property of A Graph by Changing It into Multistage Graph[J].Computing Technology and Automation,2004 23(2):52-54. [15]JIANG X W,Wang Q,JIANG Z H.The fourth version of the Proof for ZH Algorithm to Solve MSP Problem[J].Computing Technology and Automation,2010,29(3):35-48. [16]JIANG X W,PENG L H,WANG Q.MSP Problem:Its NP-Completeness and its Algorithm[C]//2010 Proceedings of the 5th International Conference on Ubiquitous Information Technologies and Applications.IEEE,2010:1-5. [17]JIANG X W.A Polynomial Time Algorithm for the Hamilton Circuit Problem[J].arXiv preprint arXiv:1305.5976,2013. [18]JIANG X W,LIU W W,WU T J,et al.Reductions from MSP to SAT and from SUBSET SUM to MSP[J].Journal of Computational Information Systems,2014,10(3):1287-1295. [19]FAN S,JIANG X W,PENG L H.Polynomial-time heuristic algorithms for several NP-complete optimization problems[J].Journal of Computational Information Systems,2014,10(22):9707-9721. [20]JIANG X W,WU T J,LI P K,et al.A New Algorithm for the MSP Problem[J].Computing Technology and Automation,2016,35(1):60-70. |
[1] | 高吉吉, 岳雪蓉, 陈智斌. 针对经典排序问题的一种新算法的近似比分析 Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling 计算机科学, 2021, 48(4): 37-42. https://doi.org/10.11896/jsjkx.200600064 |
[2] | 刘江, 周鸿昊. 一种布尔公式的代数逻辑约化新方法 New Algebraic Logic Reduction Method for Boolean Formula 计算机科学, 2020, 47(5): 32-37. https://doi.org/10.11896/jsjkx.190400018 |
[3] | 吴添君 姜新文. MSP问题NP完全性研究 On NP-completeness of MSP Problem 计算机科学, 2015, 42(7): 12-14. https://doi.org/10.11896/j.issn.1002-137X.2015.07.003 |
[4] | 周 旭,李肯立,乐光学,朱开乐. 一种加群Z上离散对数问题的DNA计算算法 Fast Parallel Molecular Algorithm for Solving the Discrete Logarithm Problem over Group on Z DNA-based Computing 计算机科学, 2012, 39(4): 232-235. |
[5] | 樊硕,姜新文. SAT问题可多项式归结到MSP问题 Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem 计算机科学, 2012, 39(11): 179-182. |
[6] | 张琨 王珩 刘凤玉. 一种时延约束的多点到多点组播路由启发式算法 计算机科学, 2005, 32(4): 107-109. |
[7] | 王元珍 裴小兵. 基于Skowron分明矩阵的快速约简算法 计算机科学, 2005, 32(4): 42-44. |
[8] | 张静 汤红波 李鸥 胡捍英. 单播和多播QoS路由问题研究及解决方法 计算机科学, 2005, 32(3): 36-38. |
[9] | 李燕 王秀峰. DNA计算方法 计算机科学, 2004, 31(5): 142-143. |
|