Dr. Du,

Papers that claim P=NP require to be rather clear in presenting the arguments given the overwhelming evidence up to date. The reviewer is noting that it is possible the explanation you provided requires refining, but the comment is vague. Are there any other more concrete observations? I would be glad to be of some assistance since NP-completeness is one of my areas of interest.

Kind regards.

The comment of the reviewer is not about the title of your paper, but rather about the structure of the whole paper. Since your claim is a really serious one, the reviwer requests for a clear and well written proof so that its correctness can be without doubt.

As far as i know because journals of computer science get hundreds of supposed proofs of either P=NP or P!=NP the editors request clearly structured and easily read papers in order to assign them to reviewers.

However, a proposed title could be "A polynomial-time algorithm for the Hamilton Cycle problem".

I agree with John Serris; the comment provided is saying the editor could not follow your proof as you presented it in the paper, it is the entire paper that was not clear to the editor.

The editor demonstrated they understood the title by saying: "a polynomial-time algorithm for the Hamilton Cycle problem", which is also a fine title. You did not have to say "a detailed proof" in your title, just have the proof in the paper.

When the editor says: "A paper making such a claim has an extraordinary burden to present its proof clearly and in a manner that can be readily checked by experts", they mean that, although your proof would obviously have to be something novel, you must still start from the basic mathematics and long accepted conventions of proofs and notations that existing mathematicians can understand immediately.

I haven't seen your paper, but in reviewing other papers I have seen students invent whole new (and flawed) methods of proof, make appeals to "obviousness" that was not present, make appeals to "common sense" or make presumptions they don't justify and which are not self-evidently true.

Your proof must flow from the existing body of published work in mathematics or computer science with citations for anything that isn't in a common textbook (and if the textbook has citations, use them too).  Any new tools, approaches or methods you use must be proven, and grounded in what we already know and proved using standard accepted methods of proof.

Somebody skilled in the art (like the editor) should not encounter any passages in the paper they do not understand, or doubt are true, or just cannot follow.

Thanks to all who concern this question.

I think my algorithm and proof should be understood. The following is my explanation:

For each main segment, we construct a broad cycle which contains this main segment. Except the four vertices of the main segment, the positions of other n-4 vertices are arbitrary. We do not need to get all the permutations of the n vertices, but only need to prove that at each big step we can get a useful cut and insert to make a main segment’s breaks become less until a Hamilton cycle is got. So, at first, each broad cycle may contains many breaks. We only let these breaks become less and less by useful cut and inserts on the broad cycles of the broad cycle set (updated continually). But why do we need the four vertices of a main segment? Because when we keep a main segment, we can get the lemma 2 and the corollary 3.2.

How to understand this proof? First a useful cut and insert: after such a cut and insert we can get a main segment’s new broad cycle which contains this main segment and has less breaks than this main segment’s old broad cycle. The algorithm has two big stages: the first stage is from the beginning until all two breaks broad cycles of useful main segments are got; the second stage is from the end of the first stage until a Hamilton cycle is got. We can check that for all k (k>=17) vertices graphs, in the first stage, at any step, we always have a useful cut and insert until the first stage is finished. Then we prove that if we add a vertex to the graph to destroy the useful cut and insert, we always can get another useful cut and insert, see this in lemma 5. In the second stage, the key is to understand the corollary 3.2.

The lemma 2, 3, 4 and the corollary 3.1 and 3.2 are clear and easy to understand. They are the basic logic and the foundation of the whole proof.

The whole proof has two key points. One is the lemma 5. It seems that only lemma 5 is enough to prove the algorithm. But the lemma 5 holds only for broad cycles with two or more breaks. The other is the corollary 3.2. It means that the good cut and inserts (step by step) on two breaks broad cycles of useful main segments have single direction (i.e., the main segments of two breaks broad cycles cannot repeat). It and the lemma 5 guarantee that we always can get at least one final two breaks good broad cycle. For the whole proof, the most important key point is the corollary 3.2, because for the two big stages of our algorithm, the goal of the first big stage is easy to get in any way.

As I detailed in private email, Peter and I came to similar recommendations; although Peter understood more of what you were doing than I did!

Even if experts in graph theory would understand what you are doing, make the effort of precisely defining and explaining the labels you are using for objects and procedures, as Peter lists.

First, understand that an actual breakthrough proof can run as many pages as it takes, it will get published if it passes peer review. Second, there is peer review: Smart reviewers will recognize that you are including some definitions just to be thorough, and will appreciate being able to verify you are using precisely the same definition as they are, but then the reviewers will likely suggest deleting the definitions or explanations that comply with standard usage. You include them, even if they are destined to be deleted, to reassure the reviewers that what you mean by a "useful cut" is precisely the same as what they mean by a "useful cut".

In this way, the reviewers ensure that when readers of the published paper encounter the phrase "useful cut" they will be correct in assuming it means what they have been taught it means, and what it means in every other paper where the phrase is encountered.

That said, keep such definitions short, if possible in footnotes or (even better) in references to textbooks; along the lines of "A 'useful cut' is a term of art in graph theory we use in its standard sense; namely a division of a subset of nodes such that ...".

Dear Professor Peter T Breuer and professor Anthony Castaldo: 

Thank you for your answers.

all th terms I have defined.

"a useful cut and insert" is a whole concept.

I need help by careful reading and thinking, and then understanding, not by assumption. I really think logically my paper can be understood.

the next is the newest version of my paper: (I attach it here: dlproblem80.pdf.)

Lizhi Du 

 Dear Professor Peter T Breuer:

Your answer is helpful to me. Thanks a lot.

I think that the main problem is not the English expression, but is that one should pay his time on the train of thoughts of the paper, carefully read, think and then understand it.  I know my English expression is not good, but I really think that the train of thoughts of the paper can be understood. Its logic is clear.

Lizhi Du

Lizhi: When you say, "I think that the main problem is not the English expression, but is that one should pay his time on the train of thoughts of the paper, carefully read, think and then understand it."

Who are you talking about? If you mean that the *reader* should pay his time, then no, you are wrong, and yes, the main problem is indeed the English expression.

For any reviewer or editor reading the paper, your proof should be a series of obviously true statements and observations that link them together. Every one of the proofs and statements they read should make them think "yes, that is true."

New proofs of long-standing problems are seldom found by obvious observations. They are typically found by observing something true nobody else has seen, by finding a new point of view or new relationship between problem components or by a creative twist that casts an existing problem as the same as a problem already solved in another discipline.

The burden is not on the reader to understand you, the burden is upon you to write in a way the reader can readily understand, and follow, and have no logical choice but to accept your overall premise as true. And because your overall premise is P=NP, readers will struggle hard to find problems with every step in your chain of logic, because your editor and reviewers will most likely believe strongly that P != NP. Which in turn means your writing and "expression" must be crystal clear at each step.

Do not blame others for failing to understand your genius. As I tell students, if they are as smart as they think they are, they should be able to solve the puzzle of how to communicate their ideas in a simple way that others can understand. One simple step at a time.

You can count on the fact that your editor and reviewers will be PhD level intellects that have been published themselves, and somewhat familiar with the problem. But speaking as a reviewer myself, do not count on us to put a great deal of time and effort into understanding your paper. We do that work for free and no credit or recognition, often on top of 12 hour work days dealing with classes, struggling students, administrative duties and our own research. When we agree to do it, we think we are giving away two or three hours, or at worst an afternoon, to do our fair share of a policing job that has to be done.

Our free work does not obligate us to work hard on your behalf. The opposite is true: If I am giving up several hours of my small allowance of free time in order to read a paper and write a review, the writer better have worked hard to make my reading an easy job. The burden of hard work is all on you, not on the reviewer. You have to make their review easy, and if they do not understand what you write, that is not their fault, it is yours.

I say all that in the spirit of helping you to get published; on this theory or some future work. For myself, I sometimes find that the process of making a proof simple, straightforward and bulletproof reveals a flaw I had not considered. That too is a useful discovery that can focus your work, or at least prevent you from publishing something false that must later be withdrawn or retracted by the journal.

Dear Professor Anthony Castaldo and Professor Peter T Breuer:

Thank you for your answers. Your answers are meaningful to me.

One who may carefully read and think and then understand my paper must have two:

1,has patience and does not have such a preassumption: this unknown man can not solve such a famous and hard problem, so it MUST be wrong.

2,very strong in computer algorithm (or high ability on thinking).

Only very little people are very strong in computer algorithm.

If I improve my English expression, this is a little help to the reviewer. But it is still very or the same hard to understand the paper. If he or she does not have the above two, he or she still can not understand my paper.

I know my English expression is not good, but I really think that the train of thoughts of the paper can be understood. Its logic is clear.

Dear Professor Peter T Breuer :

Thank you for the answer. I understand. I will try to do something according to you and I also need help from you or from other people.

Thanks a lot!

By the way, I really think to write a program from my algorithm is easy and clear, I donot understand why not.

Lizhi Du 

Lizhi: On the contrary, your unknown status has no effect on me. As a scientist, I give exactly zero points for an author being "known" or admired or a great and respected scientist. I would not give Albert Einstein the benefit of the doubt.  That is my job and commitment as a scientist, to accept only real proof, not proof by celebrity, or proof by insistence, proof by authority or proof by fervent belief. None of those are logic, and if you think about them for a second, you will realize they are all very *emotional* responses, the very opposite of a rational response.  I am committed to reason in science.

So, likewise, an assertion is not disproved by a lack of credentials, personal circumstance, or anything else but clear logic.

As for whether P=NP being "such a hard problem," I agree, it is hard. It is not your lack of celebrity that makes me doubt your proof, it is your inability to explain your proof to me in terms I accept as rational. Now that may be my own incompetence in your field. But I think your wish that somebody will do many weeks of work for you to understand what you mean and then do you the favor of translating that into the correct language of science is a fantasy.

It is up to you to make it clear. And, barring an incredible stroke of luck, in order to make it clear you will have to use the language, style, and framework of proof your reviewers *expect* you to use. They will forgive a few deviations from that, but not many.

You submitted your proof to a journal, and it was rejected. I guess my final suggestion is to begin a period of self-education by reading several previous issues of that journal, *not* for the proofs published there, but to extract, for your own use, a "template" of how a paper looks that they accept for publication. Make yourself a generalization of the layout. For example, how detailed and how long is the typical abstract? Or the typical introduction? How many figures are presented? How many steps of proof are there? How many sections? How long or short can they be? How much text of explanation versus mathematics? How many new terms are introduced, how are they introduced? If you can, copy common phrases used in proofs and exposition so you can use them as-is in your own paper.

In short, what does a published paper *look* like, and what does it *sound* like?

If you can find other papers that describe the Hamiltonian problem (for example the first proof or a textbook proof that it is NP), use that notation, or find the notation most recently used in a published paper. Do not invent your own notation.

If you believe in your proof, it should be worth the work effort required to get it published. But you will have to explain it in the language and form that reviewers expect and understand. A hundred examples of that language and form can be found in the very journals you want to publish your proof, it is what they *have* published already. You don't have to understand those articles or their math in order to generalize a framework for your own paper, and acquire the language phrases and sentence structures already accepted by reviewers and published.

P.S. I understand you think the proof is hard to understand. Making it even harder to understand by using the wrong language, wrong terminology (or invented terminology) and wrong notation just increases the probability that a reviewer will abandon their effort to understand it, and recommend rejection of your paper for lack of clarity.

Thanks to Professor Peter T Breuer  and Professor Anthony Castaldo!

I need more comments and then I can do something according to these comments.

I have used some terms and expression revision from Professor Peter T Breuer.

to Professor Peter T Breuer's latest answer: I already thought and did.

Some Chinese suggest to cooperate with a English speaking sciencist who is strong in algorihm, it may be a good idea.

Thank you very much!

Lizhi Du

To professor Peter:

What you think I should do, I already did. Not only did, but also thought deeply.

Thank you and wish to discuss directly on the algorithm and the proof. My English is not good but I feel that you can  know what I mean by your quick brain and I think I can understand you.

Surely it is a hard job for me to express myself in English.

I really think that a editor or a reviewer or a scientist can let his students write a program on the algorithm and then may trust something. This should be done easily and clearly.

Thanks a lot.

Lizhi: I think you misunderstand this process.

You have to do the work.

You have to write the program.

You have to run the program.

You have to compose the results into a table and compare them to the best known methods of solving the problem.

If you have students that work for you, you can perhaps get them to do that work.

A journal is not a place where you get to throw some ideas out and expect other people to work on them for free and then give you the credit.

We have our *own* ideas for research to work on. A journal is a place to publish your own work, not to ask for work. The reviewers are there as police, to ensure your work makes sense and did not break any laws of physics, mathematics, or logic.  And although the police are public servants, they are not there to help *you*, they are there to protect the readers of the journal from being exposed to bad science.

You seem very stubbornly attached to the idea that you should not have to do anything else on this project, and that you are not going to do any more work. In my opinion, you will not get it published that way. You have to do all the work of making your theorem believable, readable, and compelling. I doubt anybody will do that for you, and particularly not for free while giving you all the credit.

Even Albert Einstein was an unknown at one point, and when he was an unknown he worked all alone on all his papers until he managed to get them published. If you think you have solved P=NP, then you will have to do the same.

Dear Professor Anthony Castaldo and Professor Peter T Breuer:

Maybe there is a little misunderstanding between us due to my English, but what you said are meaningful and helpful to me and I understand what you mean. I will try to do something according to you. And in the process I still wish to get help from you or to discuss with you.

Thanks a lot.

Lizhi Du

Lizhi: You got 5 people to answer a very general question. I suggest you strive to construct your requests to require less than 15 minutes of our time to respond. In fact, if you look at existing responses to questions on this forum, the average length is about how much response you can expect to get from any question you publish; a few hundred words, perhaps.

I would also suggest you get help on elements that other Chinese or non-English speakers would find helpful, so we are not helping just one person with our response. So give us chunks you need help with for English, 100 to 200 words at a time, and I (and probably others) will help you put them in clear English, and critique them if need be.

Speaking for myself, I am willing to help with English. But I am not going to spend hours on your research instead of my own.

 Dear Professor Anthony Castaldo:

Probably I will construct a web page to declare the program (may include sorce code) in this summer vacation.

And then wish your help as following:

"So give us chunks you need help with for English, 100 to 200 words at a time, and I (and probably others) will help you put them in clear English, and critique them if need be."

Thank you very much.

A answer to Professor Peter:

for this:

The big questions a reviewer will want to know that you are thinking about and dealing with is why your algorithmdoesn't backtrack (I guess it doesn't).

surely my algorithm can backtrack! I may declare my program later.

for this:

Your paper was already getting unclear by about page 3, when it was describing the classical algorithm using subscripts.That is far too dangerous a coding technique to be relied on! It is very easy to make a coding error playing around with subscripts. Program your algorithm and see how it runs in reality.

surely thiere is no fault in this. carefully do and carefully check (no repeating vertices or no lost vertices). this is a easy job.

Thanks.

Lzhi Du

Lizhi says: >> surely there is no fault in this. carefully do and carefully check (no repeating vertices or no lost vertices). this is a easy job.

Wrong. Stop expecting others to make your job easy. I do not know how to make you understand that! Read the following capitalized words as strong emphasis: They will NOT "carefully do and carefully check" because that is NOT easy for them, it is only easy for YOU. Write what they EXPECT to see, based on how the most cited researchers in the field write about the problem. THAT is what they will find "easy" because they have already endured the headaches of understanding the most cited researchers in the field.

Everything about your paper should look exactly like other papers the reviewers are most likely to have seen. That means using already-published notation, already-published theorems and lemmas if they are available, already-published terminology and descriptive terms.

The more "new" things you introduce in your paper, the less likely a reviewer will bother to finish it. Introduce absolutely nothing new that is not absolutely necessary. And it is not absolutely necessary for you to use subscripts if the classical algorithm does not use them.

Reviewers are NOT there to be students and learn how you think about the problem. Do not expect them to do any work AT ALL of translating how you think about it into how everybody else in the field thinks about it. Go to the university library and ask a librarian to help you find journal papers that you can read.

Thank you, Professor Anthony Castaldo, I see and I will pay effort.

Dear Professor Peter T Breuer :

1, surely polynomial in the number of nodes n, NOT polynomial in the number of bits in the number of nodes n.

2, if according to you, there is a tree, the whole tree leaves are exponential, but I only consider polynomial leaves which is enough (according to my algorithm in the paper).

3, if you like, I will mail a running program to you later.

Lizhi: I think the question was WHY you only consider polynomial leaves.

A polynomial requires a constant; C in the exponent, so you make < N^C choices. If there are on the order of N^N leaves, then as N grows, you are somehow able to avoid N^{N-C} visits. But also as N grows, (N-C)/N asymptotically approaches 1.0. Which means for a polynomial algorithm, as N grows, the polynomial algorithm must get closer and closer to making "perfect" decisions. For example, if the average branching factor is 1 billion connections from any given node, and C=100, how do you manage to constrain your test branching to a maximum of 100 out of 1 billion potential paths? What allows you to be absolutely certain you can disregard 99.99999% of potential paths when they are all apparently equivalent?

I think that is what Peter means when he mentions a "magical" node for backtracking.

(Also, I am writing off the top of my head, I don't know if the arithmetic above is accurate, but I think the concept is right. Peter, feel free to correct me.)

Answer to Professor Anthony Castaldo: For me, I donot think this is the right thinking way: 

For example, if the average branching factor is 1 billion connections from any given node, and C=100, how do you manage to constrain your test branching to a maximum of 100 out of 1 billion potential paths? What allows you to be absolutely certain you can disregard 99.99999% of potential paths when they are all apparently equivalent?

How can I revise my paper's English expression: a polynomial time algorithm for Hamilton cycle and its detailed proof?. Available from: https://www.researchgate.net/post/How_can_I_revise_my_papers_English_expression_a_polynomial_time_algorithm_for_Hamilton_cycle_and_its_detailed_proof [accessed Jun 1, 2015].

My thinking way is:

For each main segment, we construct a broad cycle which contains this main segment. Except the four vertices of the main segment, the positions of other n-4 vertices are arbitrary. We do not need to get all the permutations of the n vertices, but only need to prove that at each big step we can get a useful cut and insert to make a main segment’s breaks become less until a Hamilton cycle is got. So, at first, each broad cycle may contains many breaks. We only let these breaks become less and less by useful cut and inserts on the broad cycles of the broad cycle set (updated continually). But why do we need the four vertices of a main segment? Because when we keep a main segment, we can get the lemma 2 and the corollary 3.2.

Dear Professor Peter:

its terms are still undefined: absolutely NO!

you need to answer the questions, not repeat your previous stuff.

But what exactly the question? the backtrack? what your "backtrack" means? Why I must include your "backtrack"?

At first ,I think your "backtrack" means repeat my experiment data.

Why my way can not exist? and why I must consider in such a way: "

also as N grows, (N-C)/N asymptotically approaches 1.0. Which means for a polynomial algorithm, as N grows, the polynomial algorithm must get closer and closer to making "perfect" decisions."?

This thinking way is too "fixed".

Lizhi: What is a "broad cycle"? Can you define that for me using standard terminology that a freshman CS student taking their first "Algorithms" course can understand?

As a real world problem, the human brain has 100 billion neurons with an average connectedness of 1000 links per neuron.

So presume I have a graph with one hundred billion nodes and 100 trillion links that connect two nodes. We won't worry about this being a directed graph (some neurons have far more outputs than inputs), and presume for the sake of argument there is indeed a Hamiltonian path to be found.

Knowing nothing else about the system, how does one find a four node "broad cycle" in this system? In terms a freshman CS student can understand, please.

Two different thinking ways, but you always think that your way is the ONLY way. Why you can not try to understand a much diffderent way?

If your way is the only way, directly say that NP is not equal to P, but this can not be done

Lizhi: There are not "two different thinking ways," there is only one valid "thinking way" in algorithmic science and that is the rules of logical and mathematical proof.

Whether P = NP is a mathematical question, and specifically you have to prove the number of steps to arrive at a solution in your algorithm can be described by a polynomial equation in N (for the number of nodes), with some fixed constant C as the exponent, and where C is not some function of N.

A polynomial algorithm is guaranteed to take less than N^C steps, for some fixed integer C, and for some "step" that also has a fixed integer as a maximum number of  simple operations.

NP means that guarantee does not hold. Typically that is due to combinatorial effects in the relationships of variables.

That is the case of the graph: The number of possible orders for N nodes is about N! (or maybe (N-1)! after aliasing). Because the first can be any of N, the next can be any of the remaining (N-1), etc. By Stirling's approximation, that is about ((N/e)^N) possible orderings of N nodes.

Each of those orders represents a different potential path through the graph.

When Peter says "Backtracking", he means that during your search for a path, you discover you have developed a path of A->B->C->D->... and discover you cannot proceed any further, so you have to "unwind" some of the final decisions and look for a different path.

In your algorithm, whatever a "cut and insert" is supposed to be, you obviously have to choose an unused node to "insert". How can you do that without making a bad choice?

What would be a bad choice? Choosing a node X that connects to several other nodes, because it connects to Node Y, but X is also the only way left to eventually connect to node Z which is not yet in the "cycle". By choosing Node X, which you cannot revisit once you have used it, you have prevented the algorithm from ever incorporating Node Z, and therefore prevented it from finding a Hamiltonian path.

So the question is this: Given the choice of X and Q to connect to Y, how does your algorithm know that X is the wrong choice and Q is the right choice for a node to "insert"? If you choose X and eventually discover you have exhausted all possible paths to Node Z, how do you know it is the choice between X and Q that you must start over at?

Of course I don't understand your algorithm. You asked for help, but do not seem inclined to actually do any work, I think you just want somebody to do a lot of work to understand your algorithm and then tell you it works. That is not going to happen.

Answer my question: Define "broad cycle" in terms I can understand without any terminology invented by you. If you want help with your English, this is how it proceeds and where it starts. If you just want validation, I can't help you.

A broad cycle,

4 vertices shape a main segment,

for each main segment I construct a broad cycle which contains this main segment, so I have a set of broad cycles(polynomial).

Now I do many "a cut and insert" on them to get a useful cut and insert to get a broad cycle which contains a main segment but has less breaks than this main segment's old broad cycle. then delete the old broad cycle and put the new broad cycle into the set of broad cycles.

all these are polynomial. I only need to prove that each time I can have a useful cut and insert until a hamilton cycle is got.

Understand sir? donot tell me the terms you dont know, I define them in the paper, I rewrite the paper to you again?

This is my process, tell me what your SMART "backtract" means in my process? And why my process MUST contain your smart "backtract"? Please note my process not your process, I donot need your process, understand Sir?

For an undirected graph G with n vertices, let \textit{x_{1}, x_{2}, ... ,x_{n}} denote the n vertices. A broad cycle is defined as a cyclic sequence \textit{x_{1}, x_{2}, ... ,x_{n}, x_{1}} of the vertices of G where every pair \textit{x_{i}, x_{i+1}} may or may not be adjacent in G. We call a pair \textit{(x_{i}, x_{i+1})} (including \textit{(x_{n}, x_{1}))} of non-adjacent vertices a break consecutive pair. So the number of break consecutive pairs is between 0 and n for a broad cycle.

I have not read your paper, at least not past the first half a page. I will not read your paper, until all your invented terms are gone, or I understand why you had to invent a term.

So we have made progress: A broad cycle depends on the definition of a "main segment." What is a "main segment"? Also, what does it mean for a "broad cycle" to "contain" the "main segment"?

You claim you only need to prove that each time you can have a useful "cut and insert" until a hamiltonian cycle is found; but that claim is not true. I don't know what a "cut and insert" is, but you ALSO have to prove there are only a polynomial number of THEM to execute, and the process of finding each of them is a polynomial number of operations.

In other words, you cannot have a polynomial time algorithm if one of the subroutines in it is NP-complete; you cannot hide the exponentially difficult part inside of a polynomial wrapper.

>>> you say, "Understand sir?"

No, I do not understand. I am not obligated to understand. My responding to you is a favor to you that gets me nothing at all, particularly since I suspect you are mistaken about your proof! 

It is up to you to continue this conversation on MY terms, and explain my questions, which may put your paper into a shape that I *can* understand, so I can tell you what is actually wrong with it. Or you may hit the lottery and prove P=NP (at which point I presume you will promptly forget you ever heard of me).

The algorithm you describe sounds like a divide-and-conquer strategy of some sort. I do not believe it is possible for that to work; I bet the problem is knowing that the "cut and insert" you found is the right one and will not prevent you from finding a future one.

I am not going to read your paper, as I said earlier, I will provide short responses to help you clarify it. So my questions to you are at the top of this response.

Donot read, but write a lot of words to discuss, donot read, but put a lot of questions.

I have no way and thank you very much Professor Anthony Castaldo .

Peter T Breuer:

all your answers mean that you are a ......If I meet a Chinese whose brain as you, I never have interest to discuss with him.

I tell you again and again all these are in my paper, I can not say a little words to explain it .Understand?

You know -(-1)=+1. So rubbish said rubbish  is a excellent job. Go.

Dear Professor Peter T Breuer:

If you said so, you are right.

Now you seem not have enough time. Some time later, If you have enough time, wish to communicate with you and get help from you.

I had the program early and I try to do some explanation.

Thank you very much!

Lizhi 

Dear Professor Peter T Breuer:

I will mail a program to you in this summer vacation.

I can immediately mail a program to you, but I am afraid that You may feel it is hard to handle. So I will change something and add some explanation.

Lizhi 

Lizhi: Your "broad cycle", since each x_i, x_{i+1) need not be adjacent, is just one of the orderings of nodes. It is not a cycle at all, because it does not have to beconnected. So you have just chosen one of (N-1)! possible orderings of nodes.

(assuming "adjacent" means directly connected by a link, in the graph one can travel directly from x_i to x_{i+1}.)

Choosing some random order of nodes does not inform the problem at all. 

Let us start with something simple, and then expand upon it. I ask you to consider the following simple graph of nine nodes, numbered 1 to 9. There is only one Hamiltonian cycle, namely the order of their appearance in pi:

3>1>4>5>9>2>6>8>7>3, with "X>Y" notation meaning a link exists from X to Y.

We will also use a question mark, X?Y, to indicate there is no link from X to Y.

Presume for now there are no other links in the graph.

Suppose I select the order of nodes (1,2,3,4,5,6,7,8,9) as my starting "broad cycle", which I will just call a candidate ordering, since it is not a cycle at all. It is just as likely as any other sequence.

Given that order, I have 1 ? 2 ? 3 ? 4 > 5 ? 6 ? 7 ? 8 ? 9 ? 1). The only actual connection in this order is that 4>5. 

From your vague description of your algorithm I gather you intend to transform this candidate ordering into a different candidate ordering, that somehow you will "cut and insert" to reduce the number of "?" in this sequence.

So what is the next simple step in your algorithm?

Using this graph, show me an example of a single "cut and insert".

(Obviously in this graph a Hamiltonian is found by starting at any node and following the one and only link available; but that is not information you are allowed to use. Your algorithm must be general, so even if I create this graph with two links off any node, only one of which can lead to the Hamiltonian, your algorithm must still work. I have a simple way of constructing such graphs, and that is what I will test your answer with.)

Peter: I don't know how the four vertices come in, either. In the example I give, the only Hamiltonian is a ring of all 9 vertices. There are no rings of just 4 vertices, or any other number, just all 9 of them. Picking 4 arbitrary points does no good. If they happen to be connected they are connected in a line, and that line cannot be "cut", it is a finalized segment of the Hamiltonian. In a complex graph with many connections between nodes, we could not even know that much.

I suspect Lizhi has mistakenly put a polynomial wrapper around some polynomial functions and does not realize that he must execute those polynomial functions a Non-Polynomial number of times. I think that the NP time is hidden in his explanation as "I do *many* cut and insert..." (emphasis mine).

How many? As many as it takes, I guess, but in the worst case, I suspect that kills the polynomial claim.

I don't know much about Hamiltonian paths, but I trust that if a simple divide-and-conquer approach was possible for this, it would have been discovered by, say, Hamilton, circa 1860, or at least by Dirac or others working on it in 1960.

Based on that, I strongly doubt any sub-graph approach, greedy algorithm, or some divide-and-conquer approach will convert this from NP to P. I think all those approaches are just too easy to have not been tried by some genius in the first hundred years of tackling this problem. (I don't think they were *smarter* than us, but I do think they were as capable and picked all the low-hanging fruit in problems anybody cared about, and this was one of those.)

That is not proof, I am ready to be surprised, but I would be astonished if those publishing proofs about Hamiltonian graphs have, for decades on end, missed a divide and conquer approach that actually works.

I don't get the "start with 4 vertices" either. That is not necessarily a cycle, because even in my simple example of 9 vertices with 9 edges, it is impossible to form a cycle with 4 vertices, or anything less than all 9 of them.

The best you can do is form a path, but I fail to see how that helps, in a more complex graph finding a 4 vertex path of A>B>C>D can in fact be the death of the Hamiltonian, which may conceivably require the segment A>C>D>B. So again we are left with the question, how do we know which of the possible 4 vertex paths will be a valid starting point for a Hamiltonian?

To the two Professors: you can download my .exe file for the Hamilton cycle problem in my new question.

Hi, every friend and expert, I just asked a new question including .exe and paper download, Thank you for your attention