Proof of the P versus NP problem: The number system hidden inside the SAT problem
Keum-Bae Cho · arXiv (Cornell University) · 2014
This paper gives a novel approach to analyze SAT problem more deeply. First, I define new elements of Boolean formula such as dominant variable, decision chain, and chain coupler. Through the analysis of the SAT problem using the elements, I prove that we can construct a k-SAT (k>2) instance where the coefficients of cutting planes take exponentially large values in the input size. This exponential property is caused by the number system formed from the calculation of coefficients. In addition, I show that 2-SAT does not form the number system and Horn-SAT partially forms the number system according to the feasible value of the dominant variable. Second, I prove the non-existence of polynomial time algorithm for k-SAT through logical approach. During this proof process, I show that the number of calculation steps needed to extract an unsatisfiable clause group is not polynomially bounded due to the formation of the number system. Then, I verify the result once more through arithmetic approach. During this proof process, I introduce the concept of dominance-reflecting inequality and I show that clause-grouping must be executed to acquire the dominance-reflecting inequality before using the linear combination rule. In addition, I prove that the number of calculation steps needed to clause-grouping is not polynomially bounded. The necessity of clause-grouping becomes a foundation for the proof of the non-existence of polynomial time search algorithm and the exponential property caused by the number system becomes a foundation for the proof of the non-existence of polynomial time estimation algorithm. This result leads to the conclusion that P is a proper subset of NP. Finally, I suggest a new algorithm to generate a hard SAT instance based on the exponential property of the SAT problem.