Computer Science ›› 2020, Vol. 47 ›› Issue (7): 820.doi: 10.11896/jsjkx.191200176
• Computer Science Theory • Previous Articles Next Articles
JIANG Xinwen
CLC Number:
[1]THE CLAY MATHEMATICS INSTITUTE.P vs.NP Problem [EB/OL].https://www.claymath.org/millenniumproblems/pvsnpproblem. [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):7886. [4]COOK S.The importance of the P versus NP question[J].Journal of the ACM (JACM),2003,50(1):2729. [5]THE CLAY MATHEMATICS INSTITUTE.Millennium Problems [EB/OL].https://www.claymath.org/millenniumproblems/. [6]KAYAL N.The complexity of the annihilating polynomial[C]//2009 24th Annual IEEE Conference on Computational Complexity.IEEE,2009:184193. [7]DEOLALIKAR V.P≠NP [EB/OL].https://www.win.tue.nl/~gwoegi/PversusNP/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):781793. [10]VALIANT L G.Quantum circuits that can be simulated classically in polynomial time[J].SIAM Journal on Computing,2002,31(4):12291254. [11]KNUTH D.All questions answered[J].Notices of the AMS,2002,49(3):318324. [12]GASARCH W I.The p=?np poll[J].Sigact News,2002,33(2):3447. [13]GAREY M R,JOHNSON D S.Computers and intractability:A guide to the theory of NPcompleteness [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):5254. [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):3548. [16]JIANG X W,PENG L H,WANG Q.MSP Problem:Its NPCompleteness and its Algorithm[C]//2010 Proceedings of the 5th International Conference on Ubiquitous Information Technologies and Applications.IEEE,2010:15. [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):12871295. [19]FAN S,JIANG X W,PENG L H.Polynomialtime heuristic algorithms for several NPcomplete optimization problems[J].Journal of Computational Information Systems,2014,10(22):97079721. [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):6070. 
[1]  GAO Jiji, YUE Xuerong, CHEN Zhibin. Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling [J]. Computer Science, 2021, 48(4): 3742. 
[2]  WU Tianjun JIANG Xinwen. On NPcompleteness of MSP Problem [J]. Computer Science, 2015, 42(7): 1214. 
[3]  . Proving NPcompleteness of Polynomial Reduction from the SAT Problem to the MSP Problem [J]. Computer Science, 2012, 39(11): 179182. 
