Answer to P/NP Problem is P≠NP
Wen Bang-yan · 2010
In this paper we answer the P/NP problem,using a simple logical analysis method,creatively proposing that the classification standards must meet the five requirements of logical compatibility,functional compliance(in line with the purpose of classification,and the binary results,yes or no on the objects to be classified,are clear and definite),and operational definiteness(unambiguous verification of meanings,and clear categorization of the virtual world and the real world).Based on the logical analysis of the and definitions,the correct conclusions of the computational problems can not be deduced in the polynomial time,as the virtual world on which the non-deterministic polynomial algorithm used in the definition relies is assumptive and magic,and can not come true in the real world.Thus the classification conclusion(NP is a subset of P) of class computational problems can not be drawn,and Theorem 1 is therefore proved: the answer to the P/NP problem is ≠ NP.In this paper,the hard incomprehensible class,the verification of standards,and P is a subset of NP are differentiated and analyzed,thus proving the Theorem 2: Using the currently accepted understandings,the two proof approaches of the P/NP problem can be completed.The above two theorems have proved the conclusion of P≠ in the positive and negative manner.This paper also questions the Towers of Hanoi computational problems belonging to class,points out that the polynomial transformation can only be realized on the NTM,and proposes to build a classification theory of computational problems with computational complexity based?on the logic,multivariate function theory and optimization theory of algorithms;also,the conclusion that halting problem is undecidable is questioned,and the errors of the diagonal proof are pointed out as well.