• ### A Polynomial time Algorithm for Hamilton Cycle and its detailed proof(1004.3702)

Oct. 10, 2019 cs.DS
Based on the famous Rotation-Extension technique, by creating the new concepts and methods: broad cycle, main segment, useful cut and insert, destroying edges for a main segment, main goal Hamilton cycle, depth-first search tree, we develop a polynomial time algorithm for a famous NPC: the Hamilton cycle problem. Thus we proved that NP=P. The key points of this paper are: 1) there are two ways to get a Hamilton cycle in exponential time: a full permutation of n vertices; or, chose n edges from all k edges, and check all possible combinations. The main problem is: how to avoid checking all combinations of n edges from all edges. My algorithm can avoid this. Lemma 1 and lemma 2 are very important. They are the foundation that we always can get a good branch in the depth-first search tree and can get a series of destroying edges (all are bad edges) for this good branch in polynomial time. The extraordinary insights are: destroying edges, a tree contains each main segment at most one time at the same time, and dynamic combinations. The difficult part is to understand how to construct a main segment's series of destroying edges by dynamic combinations (see the proof of lemma 4). The proof logic is: if there is at least on Hamilton cycle in the graph, we always can do useful cut and inserts until a Hamilton cycle is got. The times of useful cut and inserts are polynomial. So if at any step we cannot have a useful cut and insert, this means that there are no Hamilton cycles in the graph.
• ### Method Study on the 3x+1 Problem(1205.0845)

May 4, 2012 cs.DM
The 3x+1 problem is one of the most classical problems in computer science, related to many fields. As it is thought by scientists a highly hard problem, resolving it successfully not only can improve the research in many relating fields, but also be meaningful to the method study. By deep analyzing the 3x+1 calculation process with the input positive integer becoming greater, we find a useful way for solving this problem with high probability. By making use of the greater calculating ability of great computers and the internet, our way is a valid and powerful way for utterly solving the 3x+1 problem. This way can be expressed in three points: 1) If we can find a positive integer N, for any positive integer less than 2N, the times of dividing 2 out of its stopping time is less than or equal to N, then the 3x+1 conjecture is true; 2) This N may be big, so the calculation may be too big. Our way for solving this is: to find a positive integer K, for all positive integers less than 2K, not all the times of dividing 2 out of their stopping time for these integers are less than or equal to K, some part of these are greater than K, but the number of this part becomes less and less with the K increasing; 3) This K and the calculation may also be too big, our way for solving this is: to find a positive integer R, for all positive integers less than 2R, as above, out of their stopping time, the times of dividing 2 of some part of these integers are greater than R, also the number of this part integers does not become less immediately with the R increasing, but the increasing rate of this number is less and less until to below zero.