Re: Discussion regarding Mr. Diabys algorithm

SUBJECT--------A shocking possibility that everybody is 100% correct,
including Diaby


Dear Everyone,

The whole of yesterday night, I was finding it difficult to sleep,
because I was deeply thinking about all the Google Threads about Diaby
(incl this one).

In this article, I would like to share with you about a strong and
shocking possibility that all 4 people (i.e. David Moews, Yannakakis,
Hofman, and Diaby) are 100% right about their works.

I am sure that the above statement sounds confusing, to all those
reading this. But here is a possible explanation, and I would like
everyone to read this including David Moews, and other mathematical
experts.

Just consider the case....what if Diaby found it difficult to put his
entire idea down into mathematica Equations (refered to as exposition).
What if Diaby found it difficult to express his idea into mathematical
constraint Equations, and therefore was not able to completely define
his assignment polytope in mathematical equations. What if Diaby is
still finding it difficult to express his idea concretely into
mathematics.

In the above case, the following events might have taken place:
- Moews might have performed the polytope permutations on the an
incomplete polytope, which was perhaps not what Diaby intended his
actual Assignment polytope to be.
- Radoslaw might have formulated the 32-node TSP, based on an
incomplete polytope, which was perhaps not Diaby's actual Assignment
polytope
- Yannakakis is no doubt absolutely right regarding his Theorem 1, but
Yannakakis never said that the TSP cannot be solved by an asymmetric LP
formulation, which is what Diaby's actual Assignment Polytope is.....an
Asymmetric Assignment Polytope, but which Diaby has so far been
incapable of a good mathematical exposition.

I must honestly confess that I still haven't fully understood Diaby's
paper. And I get the gut feeling....that we need to listen to Diaby
more carefully. We need to read his paper more carefully, not only the
math part of it, but also try to understand deeper as to what is his
"idea" of "flows and layers", that Diaby is trying to formulate.

For your reference I am pasting some email conversations between me and
Diaby, that took place almost two months ago, before I joined this
particular Google thread. I am certain that after you read these, you
might conclude that Diaby is indeed finding it difficult to find a good
mathematical exposition. The email conversations are attached at the
bottom of this Post.

I would like to conclude by saying that.....Perhaps if we could all be
a little bit more attentive to Diaby, and PERHAPS IF WE COULD HELP
DIABY EXACTLY FORMULATE HIS IDEAS INTO MATH, it might lead the entire
mankind into a "black-hole result".....that P=NP.

For that we need to carefully listen to his idea by talking to him
face-to-face, not by looking at his paper, because he might just be
incapable of good mathematical expression or exposition on paper.

Are you ready for the possibility that P=NP ??? I am !!!

-Deepak


*********EMAIL CONVERSATIONS BETWEEN ME AND DIABY TWO MONTHS AGO*******

-----Original Message-----
From: Moustapha Diaby [mailto:Moustapha.Diaby@xxxxxxxxxxxxxxxxxx]
Sent: Thu 10/5/2006 1:14 AM
To: #DEEPAK PONVEL CHERMAKANI#
Subject: RE: My conclusion on Diaby's paper - P=NP, a linear
programming formulation of TSP

Deepak:

I thank you for your interest.

The model was first developed in the context of the TSP. The QAP is a
generalization I have been working on and refining for some time now.

The difficulties in developing a good exposition have been due to the
fact that there is no prior work on which my approach is based. The
idea of having feasible solutions of an LP conform to a particular
geometric pattern is something that is non-existent in the literature
(as far I know). Hence, a lot of new notions and proof approaches
needed to be introduced...

The QAP paper now has a level of refinement I am completely satisfied
with. Hence, I am in the process of re-writing the TSP paper to make it
more like the QAP paper. So, I think it might be better for you to
focus on the QAP paper at this time, as a different version of the TSP
paper (same model; improved exposition and proofs) is forthcoming
shortly. It may also be helpful for you to start your reading of the
paper with Figure 2.2 that describes the structure of feasible
solutions to the model, after you have studied the definitions of the
variables, before going into the details of the modeling.

Sincerely,

MD.


From: #DEEPAK PONVEL CHERMAKANI#
Sent: Wed 10/4/2006 12:33 PM
To: Moustapha Diaby
Subject: RE: My conclusion on Diaby's paper - P=NP, a linear
programming formulation of TSP


Ok Dr. Diaby,

I'll go through your TSP again, and I will also read ur QAP paper.

I am truly excited about your work.

Thanks,
-Deepak


-----Original Message-----
From: Moustapha Diaby [mailto:Moustapha.Diaby@xxxxxxxxxxxxxxxxxx]
Sent: Wed 10/4/2006 9:41 PM
To: #DEEPAK PONVEL CHERMAKANI#
Subject: RE: My conclusion on Diaby's paper - P=NP, a linear
programming formulation of TSP

Deepak - Your description of my approach contains some accuracies. I
think you have not fully understood the model and approach. It will
require a bit of time for me to fully explain. But, I plan to do so in
the next few days. Meanwhile, perhaps, you may want to take a look at
the QAP version of the model also. Best. //MD


-----Original Message-----
From: #DEEPAK PONVEL CHERMAKANI#
Sent: Wed 10/4/2006 11:45 AM
To: moustapha.diaby@xxxxxxxxxxxxxxxxxx
Cc: deepakc@xxxxxxx; deepak_pc@xxxxxxxx; deepak_pc@xxxxxxxxxxxx;
#DEEPAK PONVEL CHERMAKANI#
Subject: My conclusion on Diaby's paper - P=NP, a linear programming
formulation of TSP


Hi Dr. Diaby,

I have compiled a small document on your paper, which is attached.

Pls go through and give your comments. Also feel free to forward this
email to anyone u wish.

Thanks,
-Deepak


ATTACHEMENT>>>>>>>>>>>>>>>>>>>>>


Algorithm of Dr. Diaby -
http://www.business.uconn.edu/users/mdiaby/tsplp/

1.) Formulate the TSP's constraints as a Linear Program (LP), with
polynomial number of variables.

2.) Within polynomial time, the LP generates a single SOLUTION. This
SOLUTION represents all the optimal solutions of the TSP. But this
SOLUTION is by itself not a TSP tour .... it is only a result generated

by the LP.

3.) Within polynomial time, one can systematically generate a single
optimal TSP tour from this LP's SOLUTION (this is true whether the TSP
has polynomial number of optimal tours, or whether the TSP has an
exponential number of optimal tours).

4.) Within polynomial time, one can systematically generate a
polynomial number of optimal TSP tours from this LP's SOLUTION (this
is true whether the TSP has polynomial number of optimal tours, or
whether the TSP has an exponential number of optimal tours).

5.) Within exponential time, one can systematically generate an
exponential number of optimal TSP tours from this LP's SOLUTION (this
is true if the TSP has an exponential number of optimal tours).

6.) But since the definition of the TSP is to find at least one optimal

tour, therefore there is no need to even care about steps 4, and 5,
mentioned above. We only need to care about Step 3.

7.) It follows from the above 6 steps that therefore, Diaby's
Algorithm is able to find at least one optimal tour to any given TSP,
within polynomial time.

The major drawback, according to me, with Diaby's paper, is that
there is no necessity for him to draw parallels with "flows" and
"layers". I know that Dr. Diaby's intention may have been to try
explaining the concept better in terms of "flows" and "layers".
But according to me, this explanation in terms of "flows" &
"layers" is only creating confusion, because it is difficult for
one to visualize the fact that the LP SOLUTION represents all the
optimal TSP tours.
By explaining in terms of "flows" and "layers", it is difficult
to imagine that 1,000,000,000 rivers will join together and still be a
resultant-river with the size of only 100 rivers, but where the
resultant-river still represents all the 1,000,000,000 rivers. There is

no way of explaining this concept in terms of multi-commodity flows. In

fact, I cannot imagine is there is any "real-life parallel" of
explaining this concept. So I feel Dr. Diaby should remove this
explanation of "flows" and "layers".
If I were to be Dr. Diaby, I would simply write my paper within 8
pages, explaining all the 7 points mentioned above. Finally, there is
no need to even show experimental result with the 7-city and 8-city
TSP, because that's not needed. This is a proof, and so no
experiments need support this.

Otherwise, in my opinion, Diaby's algorithm is able to Polynomially
solve the TSP, and the TSP is Polynomially solvable.

- Deepak Ponvel Chermakani, IEEE Member, 4 Oct 2006
( Chairman of MENSA Singapore's Brain Modeling Group -
www.mensa.org.sg/sig )

.