Local Search Algorithm For Max Nae-(K)-Sat And Max-(K)-Sat

The algorithm is the core of the computer science. It has been a heated topic since the existence of computer science. Among so many branches the basis of each one is still algorithm.Maximum satisfiability problem is the most classic problem in theoretical computer science and also the first-proved NPC problem. Based on SAT problems, others usually are proved to be NP problem by reducing. The algorithm complexity of NPC problem is exponentially. The efficiency of algorithm is not so high that it is hard to get the results in the limited time when the scale of the problem is to a certain extent, which requires a faster means. Local search algorithm which comes from the hill-climbing algorithm has a wide range of applications in the study of such problems in NPC because it substantially reduced the scale of search and amount of computation. However, local search also has its limitation. It takes optimum relation in local area as its optimum relation in whole area, whereas the former is not equal to the later. Therefore, it is necessary to analyze the complexity of local search, in more specific terms, performance ratio.In this paper, the author mainly apply and design local search.By analyzing performance ratio, the author’s conclusions are as follows.1. List several usual algorithm of Max-SAT problem. Give the worst examples among the results of algorithm execution. Present the practical performances by the means of experimenting so that reference can give to readers.2. Analyze one-bit-flip local search algorithm by making use of the former researcher’theories in order to solve Max-3-SAT problem. Based on this, the algorithm is designed to solve Max-4-SAT problem in order to reduce the approximate ratio from10/9to16/15. Verify the feasibility of the designed algorithm by doing experiments.3. Change the thought and put forward a new local search algorithm so that it can solve the Max NAE-3-SAT problem and Prove the approximation ratio is4/3; the algorithm can be modified and applied to the Max-k-SAT problem and approximate ratio can prove to be(2k)/(2k-1).It also prove that it can be extended to the Max-(k)-SAT problem.