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.
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.