Computer Science ›› 2020, Vol. 47 ›› Issue (7): 8-20.doi: 10.11896/jsjkx.191200176
• Computer Science Theory • Previous Articles Next Articles
JIANG Xin-wen
CLC Number:
[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] | GAO Ji-ji, YUE Xue-rong, CHEN Zhi-bin. Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling [J]. Computer Science, 2021, 48(4): 37-42. |
[2] | WU Tian-jun JIANG Xin-wen. On NP-completeness of MSP Problem [J]. Computer Science, 2015, 42(7): 12-14. |
[3] | . Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem [J]. Computer Science, 2012, 39(11): 179-182. |
|