Font Size: a A A

Research On The Proof For Z-H Algorithm To Solve MSP Problem

Posted on:2017-01-27Degree:MasterType:Thesis
Country:ChinaCandidate:P K LiFull Text:PDF
GTID:2428330569498925Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
P vs.NP problem has been one of the most complex problems in the field of theoretical computer science,and even has been listed as the first of the seven mathematical problems in the world.P vs.NP problem has attracted many scholars in the world for its research,unfortunately,it still did not get widely recognized conclusions.In the research of P vs.NP problem,the exploration of NP complete problem is a key breakthrough,which not only lays the foundation for the relationship between P and NP,but also has a profound influence on many scientific and applied fields.This paper focuses on MSP problem that has been proved to be NP-complete problem.This paper is based on literature[1] and further studies MSP problem.The main works of this paper are as follows:1.Gives a more detailed proof of the algorithm.Literature[1] is more concerned about the idea and framework of proof,therefore,it did not give full details about the proof of the correctness of the algorithm.Thi paper mainly focuses on the details of the proof and gives the detailed process of the correctness proof of the algorithm in the end.2.Summarizes and proves some properties of algorithm.In the analysis of the algorithm for solving the MSP problem,the main process of the algorithm is analyzed,and two important properties of the algorithm are obtained and proved.3.Gives new understandings and interpretations about MSP problem and its solution algorithm,finds some of the new properties and interpret the role of the algorithm from a new perspective.The detailed proof of the algorithm for solving MSP problem in this paper further verifies the correctness of the algorithm.The new properties of algorithms and the analysis of the algorithm process and its role from the new perspective also provides an important reference for the study of MSP problem,and provides important help for the further improvement of the research on this problem.
Keywords/Search Tags:NP complete problem, MSP problem, algorithm analysis, polynomial algorithm, correctness proof
PDF Full Text Request
Related items