On The NP-completeness Of The MSP Problem

Since Cook?s proof of the first NP-complete problem, large numbers of NP-complete problems with wide applications have been discovered. For instance, the SAT problem is a classical problem in logic and circuits; the Coloring problem is foundamental in combinatorial optimization; the Sub-graph Isomorphism problem stands at the kernel of pattern matching; and the Subset Sum problem is applicable for public key encryption. To determine the existence of a polynomial-time algorithm for NP-complete problem(i.e., the problem of whether NP=P) is a long-held challenging problem. No matter whether NP=P or NP ?P, the study will result in a better understanding of the problem itself and even the human thinking process in general.Recently, more and more researchers have begun to question the meaning of studying the P versus NP problem. K nuth pointed that "… probably in the next fifty years, somebody will prove that P = NP… Now, that would be the worst possible solution to the problem, because it could never, ever have any use at all, it just would mean that the question was the wrong question to ask. " [56] Even so, as one of the seven Millennium Prize Problems, the P versus NP problem is still the Holy Grail in theoretical computer science. Every time when a ?proof? was pronounced, it would arouse fierce discussions among scientists and the public. This problem appears fairly easy while turns out intractable, and many seemingly prosperous methods finally ran into corners and forced researchers to start over. There is hardly any substantial progress in the last 50 years.Literature [1] proposed a novel NP-complete problem called MSP and proposed a polynomial- time algorithm named Z-H, which provides a new method for studying NP-completeness. It was posted to Transactions on Algorithms and no errors have been fedback from the reviewer. 53,000,000 random instance of MSP was used for testing the algorithm from late 2010 to early 2014. No error was found.Supported by NSFC(No. 61272010) and based on the research in [1], we studied the property of the MSP problem and designed diverse models for testing Z-H algorithm. Our works can be concluded as follows:1. Through problem reductions, we studied the correlation between SAT, K-Coloring, Sub- graph Isomorphism, Hamilton Circle, C lique, Sub- graph Isomorphism and MSP, to explore the NP-completeness and to reveal the expressive property of the MSP problem. This laid the basis for further tests.2. We observed the phase transition phenomenon in the MSP problem, in which both the ratio of positive instances a nd the average solving time of Z-H algorithm experience sharp changes in a narrow region. We determined the order parameter and the critical value, and made a rudimentary estimation of the bound of the existence of solutions. The phase transition model can be also applied for better testing Z-H algorithm.3. Previous studies[54,55] of Z-H algorithm were only able to depict the main idea of the algorithm due to the complexity of the algorithmic steps(especially the ?C hange? operator) on certain instances(relying on intuition rather than analysis). This paper explicitly analized its dynamic features with instances of pigeonhole formulas.4. We deliberated on the the proof of the correctness of the algorithm. An instance- hybridizing method was proposed targeted at possible bugs of the ?splitting? technique used in the proof. Emperical results affirmed its feasibility.5. A general problem solver based on Z-H Algorithm was designed, for solving NP-complete problems, and more importangly, for implementing mass tests integrating above techniques(i.e., problem reduction, phase transition and instance-hybridizing). The tests were conducted by our whole research group and Professor Xu at BUAA.