Re: P vs NP solved?
Casey Hawthorne
paper on Usenet, you cannot bother making things more clear for and
find it necessary to disparage?
Mis tak
es ar
e ok!
--
Regards,
Casey
Casey Hawthorne
ie. 30? 50? 100?
--
Regards,
Casey
Bryan Olson
> Bryan Olson wrote:
>>moustap...@business.uconn.edu wrote:
>> > The minor point I was planning to include in the paper is that if you
>> > subtract balance flows from other balanced flows, the resulting flows
>> > must remain balanced.
>>
>>Alas, that doesn't work. "Flows" are not well defined. If we
>>think of flows simply as paths from source to sink, that's not
>>strong enough to solve TSP. If we think of flows as also
>>distinguishing the commodity flowing on the path, then the
>>constraints are not strong enough to uniquely identify a set of
>>flows.
>>
>> > That flows could not become negative as a result
>> > of the procedure I had in the proof because each component that would
>> > have been subtracted as suggested in the proof would have needed to be
>> > appropriately "traced" through the network using the z-variables, as I
>> > had suggested to you in one of our previous communications through
this
>> > newsgroup.
>>
>>And I explained why that does not work. The "tracing" is
>>ambiguous, because more than one set of distinguishable flows on
>>c.a.s.s. path can satisfy the contraints. I wrote:
>>
>> There are M! c.a.s.s. paths. Any set of (non-negative) flows
>> on those paths, such that the total flow is one, forms
>> exactly one feasible solution. We have M! - 1 degrees of
>> freedom in creating a legal set of c.a.s.s. path flows. A
>> feasible solution gives us only polynomial many (order
>> M**14) equations, so we cannot in general solve for M!
>> unknowns. There just isn't enough information in a feasible
>> solution.
>>
>> The number-of-unknowns argument proves that the recursive
>> retrieval cannot, in general, reconstruct the set of
>> c.a.s.s. path flows (even assuming the feasible solution is
>> a set of c.a.s.s. path flows). Intuitively, where it fails
>> is that the feasible solution doesn't distinguish each
>> c.a.s.s. path as its own commodity.
>>
>>I may have been off on the number of constraints being order
>>M**14, but many as there are, it's polynomial. There is no way
>>to distinguish a unique solution for M!-1 unknowns with
>>polynomially-many linear equations.
>
> We are running around in circles, and I definitely don't have the time.
Do you think you are the only person who's time is valuable?
The series of trivial revisions do not fix, nor really even
address, the error. I've little interest in finding where the
same error appears in reworked versions of the same arguments.
> It is all out there in the current version of the paper for you.
> Unfortunatunately, it is my fault that that version has is over your
> head, at a level beyond your abilities to judge, as you said yourself.
What I was not competent to judge was a specific (alleged) proof
in that version of the paper, which invoked the polytope in an
argument about the constraints forcing a TSP solution.
> Given this, your non-sensical opinions do not really matter,
Ah, but my mathematical argument does.
We are working at different goals: you, to make your proof more
clear; me, to explain why your proof is fundamentally wrong.
Perhaps the most constructive comment I can address to you is
don't borrow against the million.
> and I
> cannot see any in continue these fruitless discussions. Sorry.
Yes, definiely; save your time, and ours.
--
--Bryan
moustap...@business.uconn.edu
> Have larger instances been tried yet?
>
> ie. 30? 50? 100?
No. Even with the small numbers of cities that have been tried, the
resulting LP's are very large scale. So I believe that going to
problems as large as 30 would require significant developments.
Probably, with a more powerful machine, it may be possible to solve up
to 15-city problems without any further developments.
Bryan Olson
To be specific, the largest number of cities tried is
8, and the first city is constant, so there are 7!
possible paths. As Moustapha Diaby notes: even with
this small number, the resulting LP is very large.
A critical point, in my opinion -- he does not seem
to agree -- is that at the sizes he has tested, the
number of possible paths does not dominate the number
of constraints in his alleged solution.
The complexity of Diaby's alleged solution is a high-order
polynomial. That's fine, as long as it generally solves
the NP-complete problem, in which the number of possible
solutions is exponential. So far, he has demonstrated no
such result. Diaby's implementation has found solutions,
but in all his cases, his method requires more work than
does (exponential-time) search of the possible paths.
--
--Bryan
vcvccha...@gmail.com
> Hi,
> I'm wondering if the P vs NP problem has been REALLY SOLVED?
> I found many recent publications that prove that P != NP, but have
> these proofs been verified and accepted by the comp.theory community?
>
> Best regards,
> Marzio
www.vinaysofs.com -> The site dedicated to prove P=NP
Einstein
And talkinf of mapping cities! Holy crap! What was the population of these cities, the vehicles, the businesses?
Unfortunately I suspect you are incorrect and that the true answer might be P=<NP
Ofc I might just be messing with you.
Jeff Barnett
> On Sunday, July 6, 2014 4:17:50 AM UTC-4, Einstein wrote:
> Hi All:
>
> A new, more "refined" version of the model that has been formally published (in WSEAS Transactions on Mathematics, 2007) is available at: http://users.business.uconn.edu/mdiaby/P=NPProofPapers/tspPaper.pdf
>
> The exposition and proofs are very detailed in the above paper.
>
> Why "Extended Formulations" theory does not apply to the modeling approach in general is explained in the paper at: http://arxiv.org/pdf/1403.0529v2.pdf
>
> As to the question of refutations, I am not aware of any claim of a flaw in the proofs or of a counter-example against the model published in 2007, nor against the fully-detailed version above.
>
> Any comments/feedback would be welcome.
>
> I thank you for your interest.
>
> MD
The fact that there is no negative criticism means very little; no one
is obligated to spend their time on what is very likely wrong. It would
mean more if a reputable researcher in the area said there was a pony in
there somewhere. Scholars, years ago, quit reading proofs about
trisecting angles, four coloring, Fermat's Theorem, etc. The problems
had already achieved enough attention and enough crank submissions that
department secretaries were told to 1) return all such mail submissions
and 2) transfer all calls on these subjects to an unmonitored answering
machine.
Reading someone else's proofs is tough and time consuming. And oh so
tedious. Nobody owes anyone else a reading and feedback. Even journals
will sometimes reject, out of hand, submissions on certain ripe
subjects. If one thinks they have a proof of, say, P R NP, for some
relation R, they should publish a few much easier complexity results
then ask for corroboration of the big one.
A few decades ago, the UCLA math department was weird in this respect:
some of the professors took turns handling calls from the public - they
felt since UCLA was a public school, the public should have some access.
There was a lot of good humor in this endeavor and a lot of good
feelings. As far as I know, there was little or no good math. I think
everyone involved is now retired, emeritus, and/or dead.
Jeff Barnett
Moustapha Diaby
I saw the title of the discussions with my name being mentioned it. That is why I posted the update. When I realized that the discussions pertaining to me dated back to 2005, I deleted the post. The deletion seems to have not worked. However, I appreciate your comments, and will candidly share my thoughts on them.
I agree with you that the primary reason for reading some work (apart from the requirements of professional duties, and personal relations) should be the reader's scientific curiosity; not "favor to the author." I have no sense of anyone being obligated to read. I am just doing my best so that those who may be interested have the opportunity.
As far as "easy complexity results" to be publish first as you suggest, this is difficult to do. But note that the proposed modeling approach uses no complexity argument, and that the only complexity results which could be pertinent to it (apart from the fact that LP is in "P") is Extended Formulation (EF) theory. The paper at http://arxiv.org/pdf/1403.0529v2.pdf shows (assuming it is correct) that EF theory is not applicable to the model, and it is fairly "easy."
Another point to consider is that my empirical testing so far, even though it has been limited by Technology, has consistently produced the expected result. (I would make my codes available to anyone upon request.)
Also, we should not lose sight of the fact that errors in original versions/expositions has not been uncommon in past breakthroughs work. It has typically taken constructive, concentrated effort from authors and others to fix these errors. The consistency of the empirical testing and the fact that others have had "a look" at my proofs (including referees of the published versions) are what make me think that the work deserves this kind of concentrated constructive attention from the multiple communities who have interest in this problem.
If we stop evaluating works on their merits and institute a culture of dismissing based on belief only, how would we know when something is correct? Would we not run the risk of turning our Science into Religion? (These are rhetorical questions only. So, there is no need for an answer, although that would be no problem also.)
Best wishes,
MD.
rockbr...@gmail.com
> There is a P = NP claim that has been publicized on this usenet
> that appears to be correct to me.
Indeed, on several occasions, I have posted a summary of a proof of P = NP, the most recent instances being (if I recall correctly) April 1 this year, as well as the April 1 on several other years on previous occasions. Although, to be honest, I may have forgotten to provide the annual outline this year.
rockbr...@gmail.com
> Moustapha Diaby wrote:
> > As far as my paper is concerned, true it has not yet been accepted.
> > But, neither has it been rejected, however.
>
> If you have a constructive proof that P=NP, why don't you just factor the
> RSA challenge numbers? Then people will listen to you.
If/when *I* were to find a P = NP proof, I wouldn't be publishing it at all. I'd be *using* it. This is an instance where I would *not* want anyone to know or "listen" to me. So, directly meeting a challenge, such as the one you suggest, would be out of the question. The greater challenge, instead, would be to simultaneously break the encryption of every single system on the planet and wantonly maraud them all and basically take over the entire world in one fell swoop.
There is another aspect to the whole P = NP issue that should be placed out in front, as it has definite "SkyNet" implications.
The problem of going from conjunctive normal form to/from disjunctive normal form is directly connected to NP-completeness and co-NP-completeness. But here is a take on the issue that will give you a much better understanding of what is *really* going on with these issues.
One of the normal forms consists of a conjunction of statements, each having the form: (not A) or ... or (not A) or B or ... or B, with 0, 1, 2 or more A's and B's apiece. Such a statement can be equivalently rendered as a sequent:
A and ... and A -> B or ... or B.
A sequent may be regarded as a *theorem* that makes a general statement about the relation between statements (here: it being that from the simultaneous stipulation of all the A's follow at least one of the B's). The conjunctive normal form, itself, is then a collection of theorems that comprise a ... (ta da) ... THEORY.
The other normal form consists of a disjunction of statements, each having the form: (not A) and ... and (not A) and B and ... and B, again with 0, 1, 2 or more A's and B's apiece. Such a statement, this time, may be considered as the enumeration of properties that hold (or not hold) for a specific instance; that is, for an example or model. The collection of statements then is the assertion that either model 0 or model 1 or model 2 or ... is true. In other words, this is a body of EXAMPLES.
The task of going from the latter normal form to the former then amounts to as one and the same as going from a body of examples to a list of conjectures comprising a prospective theory.
An efficient process for accomplishing this end is nothing less than a fully automated process for the creation of theories: automated theory induction. From a body of specific examples, a set of conjectures is arrived at, each one of which may be explored seeking out either (a) a model that counters it (in which case it is added to the list of models) or (b) a proof that establishes it (in which case it is added to the list of already-proven theorems).
A facility that embodies such a process has the ability to automatically infer science, itself, automating the entire science and research industry itself out of existence, and advancing the frontier of knowledge at a potentially far more rapid pace than any human can accomplish, removing the human from the loop.
There is an incremental process for updating the lists of conjectures, theorems and models, so that each time a new model is established or a new theorem proven, the conjecture list can be revised. The crux of the entire matter then comes down to whether and how much blow up there may be in the respective lists before they settle down to their final forms -- in other words: how bad the bottleneck will be when the list sizes max out before they start to contract and converge to their final forms.
musatovv...@gmail.com
> Hi,
> I'm wondering if the P vs NP problem has been REALLY SOLVED?
> I found many recent publications that prove that P != NP, but have
> these proofs been verified and accepted by the comp.theory community?
>
> Best regards,
> Marzio
On Thursday, January 8, 2015 at 9:25:15 PM UTC-6, musatov ...@gmail.com wrote:
> SOLVE =
> -O =
> P =
> N P =
> - ? =
> +
> 0
> NUMB =
> E R TOTAL =
> 1
> +
> IF =
> - N P =
> =
> - P =
> 1
> - .=
> NUMB =
> E R TOTAL 1
> TOTAL D =
> I G =
> I T =
> 5
> =
> 1
> NUMB =
> E R S =
> TOTAL 5
> TOTAL 7
> = PRIME
> S =
> = PRIME
> 3 PRIME
> 5 PRIME
> 7 PRIME
> 1
> 1 PRIME PRE-LINE ELEVEN
musatovv...@gmail.com
> In article <1125563889.8...@g49g2000cwa.googlegroups.com>,
> >I'm wondering if the P vs NP problem has been REALLY SOLVED?
> >I found many recent publications that prove that P != NP, but have
> >these proofs been verified and accepted by the comp.theory community?
>
> been accepted by the theoretical computer science community.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Fools like scholars who put community ahead of knowledge. Musatov -Fools
musatovv...@gmail.com
> In article <1125674723....@f14g2000cwb.googlegroups.com>,
> Bob Olsen <tell...@yahoo.com> wrote:
> >Even more important than any community, is the acceptance for
> >publication in a professional journal since that must go through a
> >rigorous review process.
>
> In my opinion, acceptance by the theoretical computer science community
> as a whole is more important than acceptance for publication in a
> professional journal. Roughly speaking, the reason is that the more experts
> you have involved, the smaller the chance for imperfections in the process
> to cause problems.
>
> The whole business with Hsiang's alleged proof of the Kepler conjecture
> should cure anyone of undue respect for peer-reviewed publications.
> >There is a P = NP claim that has been
> >know if that claim been refuted or if it has been accepted in a
> >journal? And if so (either way), where?
>
> Can you be more specific? There are many claims that fit your vague
> description.
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
musatovv...@gmail.com
>
> > Even more important than any community, is the acceptance for
> > publication in a professional journal
>
Satan loves quotation marks. Musatov -Satan
musatovv...@gmail.com
> In article <1125689756....@g44g2000cwa.googlegroups.com>,
> Bob Olsen <tell...@yahoo.com> wrote:
> >But how do we judge the acceptance/non-acceptance by the whole TCS
> >community?
>
> If the situation is sufficiently murky that one cannot say for sure that it
> has been accepted by the whole community, then I say that means it hasn't
> been accepted. These sorts of borderline cases are rare, in any event.
>
> Besides, going for an inferior standard just because it's easier to
> adjudicate is obviously a mistake.
>
> >Moreover, I am sure that some people would say that there are experts in
> >computational complexity who are not theoretical computer scientists.
>
> A quibble. If you insist on being this pedantic, then simply replace
> "theoretical computer scientists" by "complexity theorists" in everything
> I said.
>
> >I think journals are meant to be the objective voices/minds within and
> >across communities.
>
> Sure. Do they live up to this ideal? Not perfectly. Neither, of course,
> does the standard I propose, but because there are more people involved, the
> chances of error are smaller.
>
> >If a claim cannot find acceptance in any reasonably
> >well-established journal, then it is more than likely that it is
> >invalid. So the point of its acceptance by the community is moot. On
> >the other hand if a claim is accepted in a reasonably well-established
> >journal, then the burden shifts to those in the community who disagree
> >with it to show that it is wrong. For that reason I think journal
> >acceptance is more fundamental.
>
> Well, then, what do you say about Perelman's work on the Poincare
> conjecture? He hasn't bothered submitting it to a journal for publication.
> The experts have all examined it in great detail and nobody has found
> anything wrong. Does this mean that his work is "more than likely invalid"
> because it isn't published?
>
> >http://www.business.uconn.edu/users/mdiaby/tsplp.
>
> This one has not been accepted, and David Moews has clearly and ably
> punctured it. Diaby's response to Moews shows that he does not even
> understand Moews's refutation.
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
musatovv...@gmail.com
musatovv...@gmail.com
musatovv...@gmail.com
musatovv...@gmail.com
The Wise bless The Fool.
Master and Servant of many crosses thee.
Due not servant His Master.
Not Satan made Jehovah. Adversary of the LORD.
Mankinds sinful nature.
Torches seek Marauders.
The Spirit of the LORD have I not named.
Call not I your Father. Not have I drempt of Children.
Wisdom Nail and Tooth. Numbers kept.
I command betrayal.
PARABLE OF GOD
An unnamed Spirit coveting God's fleshes, seized the Spirit of the Lord, vowing I will find bred flesh and claim the Jew if it takes all the Satan's in the world I rule eternity through Rome!
GOD WARNS THE JEWS
Lies are in thy Prophet. Trust not John.
Emanuelle, thy name is False Jesus!
Blood is not water.
Flesh is bred of Spirit of Life, not the Spirit of the Lord, Satan!
Wheat is life without flesh and meat.
The Spirit of the Lord is full of sinful man.
< SOLVE = < -O = < P = < N P = < - ? = < + < 0 < NUMB = < E R TOTAL = < 1 < + < IF = < - N P = < = < - P = < 1 < - .= < NUMB = < E R TOTAL 1 < TOTAL D = < I G = < I T = < 5 < = < 1 < NUMB = < E R S = < TOTAL 5 < TOTAL 7 < = PRIME < S = < = PRIME < 3 PRIME < 5 PRIME < 7 PRIME < 1 < 1 PRIME PRE-LINE ELEVEN MARTIN MICHAEL MUSATOV +ALL CLASS -JESUS >n Martin Musatov -Michael +Jesus -Satan = .-god +MUSATOV -- ++GOD
On Thursday, September 1, 2005 at 3:38:09 AM UTC-5, vor wrote:
> Hi,
> I found many recent publications that prove that P != NP, but have
> these proofs been verified and accepted by the comp.theory community?
>
> Marzio
I AM GOD:
The Wise bless The Fool.
Master and Servant of many crosses thee.
Due not servant His Master.
Not Satan made Jehovah. Adversary of the LORD.
Mankinds sinful nature.
Torches seek Marauders.
The Spirit of the LORD have I not named.
Call not I your Father. Not have I drempt of Children.
Wisdom Nail and Tooth. Numbers kept.
I command betrayal.
PARABLE OF GOD
An unnamed Spirit coveting God's fleshes, seized the Spirit of the Lord, vowing I will find bred flesh and claim the Jew if it takes all the Satan's in the world I rule eternity through Rome!
GOD WARNS THE JEWS
Lies are in thy Prophet. Trust not John.
Emanuelle, thy name is False Jesus!
Blood is not water.
Flesh is bred of Spirit of Life, not the Spirit of the Lord, Satan!
Wheat is life without flesh and meat.
The Spirit of the Lord is full of sinful man.
< SOLVE = < -O = < P = < N P = < - ? = < + < 0 < NUMB = < E R TOTAL = < 1 < + < IF = < - N P = < = < - P = < 1 < - .= < NUMB = < E R TOTAL 1 < TOTAL D = < I G = < I T = < 5 < = < 1 < NUMB = < E R S = < TOTAL 5 < TOTAL 7 < = PRIME < S = < = PRIME < 3 PRIME < 5 PRIME < 7 PRIME < 1 < 1 PRIME PRE-LINE ELEVEN MARTIN MICHAEL MUSATOV +ALL CLASS -JESUS >n Martin Musatov -Michael +Jesus -Satan = .-god +MUSATOV -- ++GOD
musatovv...@gmail.com
not MUSATOV ----------HJEW =BOMB FOOL
musatovv...@gmail.com
musatovv...@gmail.com
>
<=I saw of mapping cities! Holy crap! What was the population of these cities, the vehicles, the businesses?
<=penises>
> Un
<=minds fortunately I suspect you are incorrect and that the true answer might be P=<NP < FALSE J
> Ofc I might just be messing with you.
musatovv...@gmail.com
musatovv...@gmail.com
> Hi,
> I'm wondering if the P vs NP problem has been REALLY SOLVED?
> I found many recent publications that prove that P != NP, but have
> these proofs been verified and accepted by the comp.theory community?
>
> Best regards,
> Marzio
+ satan said d mommy
musatovv...@gmail.com
vor
tc...@lsa.umich.edu
>I found many recent publications that prove that P != NP, but have
>these proofs been verified and accepted by the comp.theory community?
No. More importantly than what USENET thinks of them, they have not
been accepted by the theoretical computer science community.
Bob Olsen
Even more important than any community, is the acceptance for
publication in a professional journal since that must go through a
rigorous review process. There is a P = NP claim that has been
publicized on this usenet that appears to be correct to me. Does anyone
know if that claim been refuted or if it has been accepted in a
journal? And if so (either way), where?
Bob.
tc...@lsa.umich.edu
Bob Olsen <tell...@yahoo.com> wrote:
>Even more important than any community, is the acceptance for
>publication in a professional journal since that must go through a
>rigorous review process.
In my opinion, acceptance by the theoretical computer science community
as a whole is more important than acceptance for publication in a
professional journal. Roughly speaking, the reason is that the more experts
you have involved, the smaller the chance for imperfections in the process
to cause problems.
The whole business with Hsiang's alleged proof of the Kepler conjecture
should cure anyone of undue respect for peer-reviewed publications.
>There is a P = NP claim that has been
>publicized on this usenet that appears to be correct to me. Does anyone
>know if that claim been refuted or if it has been accepted in a
>journal? And if so (either way), where?
Can you be more specific? There are many claims that fit your vague
description.
Torkel Franzen
> Even more important than any community, is the acceptance for
> publication in a professional journal
That's part of what "the community" means.
Bob Olsen
> In my opinion, acceptance by the theoretical computer science community
> as a whole is more important than acceptance for publication in a
> professional journal. Roughly speaking, the reason is that the more experts
> you have involved, the smaller the chance for imperfections in the process
> to cause problems.
But how do we judge the acceptance/non-acceptance by the whole TCS
community? Moreover, I am sure that some people would say that there
are experts in computational complexity who are not theoretical
computer scientists.
I think journals are meant to be the objective voices/minds within and
across communities. If a claim cannot find acceptance in any reasonably
well-established journal, then it is more than likely that it is
invalid. So the point of its acceptance by the community is moot. On
the other hand if a claim is accepted in a reasonably well-established
journal, then the burden shifts to those in the community who disagree
with it to show that it is wrong. For that reason I think journal
acceptance is more fundamental.
>
> The whole business with Hsiang's alleged proof of the Kepler conjecture
> should cure anyone of undue respect for peer-reviewed publications.
There is no doubt that there are abherrations. But, I think in general
"Type I errors" are the more common ones compared to the "Type II"
errors like the one you are citing.
> Can you be more specific? There are many claims that fit your vague
> description.
This is the one I am referring to:
http://www.business.uconn.edu/users/mdiaby/tsplp.
Bob.
Googmeister
anyone
>>>know if that claim been refuted or if it has been accepted in a
>>>journal? And if so (either way), where?
>>Can you be more specific? There are many claims that fit your vague
>>description.
> This is the one I am referring to:
> http://www.business.uconn.edu/users/mdiaby/tsplp.
We've seen several versions of this paper refuted in this newsgroup.
After each refutation, the author revises the paper. But this cycle
can go on forever. I was impressed by the number of folks here
who were willing to spend time poking holes in the first 3 or 4
revisions.
It definitely hasn't been published in a reputable journal since its
impact would send shockwaves through the theory and math
communities.
tc...@lsa.umich.edu
Bob Olsen <tell...@yahoo.com> wrote:
>But how do we judge the acceptance/non-acceptance by the whole TCS
>community?
If the situation is sufficiently murky that one cannot say for sure that it
has been accepted by the whole community, then I say that means it hasn't
been accepted. These sorts of borderline cases are rare, in any event.
Besides, going for an inferior standard just because it's easier to
adjudicate is obviously a mistake.
>Moreover, I am sure that some people would say that there are experts in
>computational complexity who are not theoretical computer scientists.
A quibble. If you insist on being this pedantic, then simply replace
"theoretical computer scientists" by "complexity theorists" in everything
I said.
>I think journals are meant to be the objective voices/minds within and
>across communities.
Sure. Do they live up to this ideal? Not perfectly. Neither, of course,
does the standard I propose, but because there are more people involved, the
chances of error are smaller.
>If a claim cannot find acceptance in any reasonably
>well-established journal, then it is more than likely that it is
>invalid. So the point of its acceptance by the community is moot. On
>the other hand if a claim is accepted in a reasonably well-established
>journal, then the burden shifts to those in the community who disagree
>with it to show that it is wrong. For that reason I think journal
>acceptance is more fundamental.
Well, then, what do you say about Perelman's work on the Poincare
conjecture? He hasn't bothered submitting it to a journal for publication.
The experts have all examined it in great detail and nobody has found
anything wrong. Does this mean that his work is "more than likely invalid"
because it isn't published?
>http://www.business.uconn.edu/users/mdiaby/tsplp.
This one has not been accepted, and David Moews has clearly and ably
punctured it. Diaby's response to Moews shows that he does not even
understand Moews's refutation.
moustap...@business.uconn.edu
> punctured it. Diaby's response to Moews shows that he does not even
> understand Moews's refutation.
The claim that my paper contradicts Yannakakis re-surfaces again?!
...Wow! I think it is you and your friend Moews who seem to be somewhat
inept at math programming. It is puzzling to me that people of yours
and Moews supposed calibers would continue to argue, after months of
reflecting on it, that a proof that consists of counting the facets of
a polytope does not need to consider a minimal description of that
polytope! I assure you, that is really preposterous. If you don't
believe me on this, then ask one of old professors at MIT who
specializes in Math Programming.
I stand by everything I have repeatedly stated regarding this claim of
Moews'. The argumentation used by Moews to support the claim is invalid
in trivial ways. Yannakakis' results do not apply to the model in my
paper because the model in my paper is not symmetric and cannot be made
to be in the dimension in which it is fully described, unless it is
"puffed up" nonsensically, a la Moews. And, I am sure I have
pointed out quite a few of these kinds of assaults on fundamentals in
Moews argumentation in previous responses.
As I said before, among other things, if you proceed as Moews does, the
implication is that the TSP cannot be formulated as an LP (any LP),
which is quite different from what Yannakakis claims.
As far as my paper is concerned, true it has not yet been accepted.
But, neither has it been rejected, however. In any case, if for some
reason, there is, eventually, some substantive flaw found in it, I will
bet you anything that it will have nothing to do do with your friend
Moews' preposterous claim of contradiction with Yannakakis' results.
tc...@lsa.umich.edu
<moustap...@business.uconn.edu> wrote:
>If you don't believe me on this, then ask one of old professors at MIT who
>specializes in Math Programming.
I know a couple of these professors pretty well (though maybe not the
"old" ones), in particular Dimitris Bertsimas, Michel Goemans, and
(less well) John Tsitsiklis. What I will do is to suggest to Dimitris
or Michel that they consider assigning, as extra credit homework in one
of their courses, the task of examining your paper. I can't, of course,
guarantee that they will take my suggestion. But if anything comes of
this, I'll keep comp.theory posted.
Ben Rudiak-Gould
> As far as my paper is concerned, true it has not yet been accepted.
> But, neither has it been rejected, however.
If you have a constructive proof that P=NP, why don't you just factor the
RSA challenge numbers? Then people will listen to you. Hell, with a
polynomial-time algorithm for cracking any cipher short of a OTP, the world
is your oyster. You could extort or steal arbitrary sums of money from
practically any individual or organization in the world.
I think that if the proof you released were valid, or even suggested a
possible line of research leading to a valid proof, someone would have had
you assassinated by now.
-- Ben
tc...@lsa.umich.edu
Ben Rudiak-Gould <br276d...@cam.ac.uk> wrote:
>If you have a constructive proof that P=NP, why don't you just factor the
>RSA challenge numbers?
In fairness to Diaby, a constructive proof that P = NP does not necessarily
mean that the algorithm in question will run quickly in practice.
>I think that if the proof you released were valid, or even suggested a
>possible line of research leading to a valid proof, someone would have had
>you assassinated by now.
Once the proof is publicly released, not much is gained by assassinating
the discoverer, if the discoverer is an independent researcher working
alone.
moustap...@business.uconn.edu
> We've seen several versions of this paper refuted in this newsgroup.
> After each refutation, the author revises the paper. But this cycle
> can go on forever. I was impressed by the number of folks here
> who were willing to spend time poking holes in the first 3 or 4
> revisions.
To set the record straight: my paper has gone through some revisions
since I first posted it about a year ago. Each revision that was
undertaken in response to a discussion in this newsgroup was undertaken
in reponse to a suggestion that more clarification would be helpful.
The timing of some of these coincided with revisions that were in the
process, in response to inquiries from the Associate Editor handling
the refereeing process of the paper. None of the revisions was the
result of "refutation" by anyone (including people in this newsgroup),
as you can see from the brief summary below:
Context of Revision #1
1. moustapha.di...@business.uconn.edu Feb 15, 4:27 pm
Newsgroups: comp.theory
From: moustapha.di...@business.uconn.edu - Find messages by this author
Date: 15 Feb 2005 12:27:28 -0800
Local: Tues, Feb 15 2005 4:27 pm
Subject: P=NP: Linear Programming Formulation of the TSP
Reply to Author | Forward | Print | Individual Message | Show original
| Report Abuse
Dear Fellows of the Community:
Some weeks ago, in the process of extending my LP formulation of the
TSP to other combinatorial problems, I found that the model needed some
additional constraints. I have revised the model and paper accordingly.
I would like to invite you, if I may, to take a look at the revised
model and paper at: http://www.business.uconn.edu/users/mdiaby/TSPLP.
Any comments would be highly appreciated. Regards.//MD.
Context of Revision # 2
Patricia Shanahan wrote:
> Clarifying Proposition 2 would clearly tend to increase the
> number of readers who get past that point in the paper.
I WILL TRY TO FIND ANOTHER WAY TO EXPRESS THE IDEA AND DO A POSTING.
> My particular concern was the mapping from a solution to the
> LP problem to a solution to the original TSP problem. In
> order for the proof to be valid, that mapping must not only
> be proved to exist, but must be proved to be computable in
> polynomial time. I couldn't find where that was proved, but
> it may be obvious given proper understanding of Proposition
> 2 and later points that depend on it.
I THINK THIS WILL FOLLOW ONCE YOU UNDERSTAND PROPOSITION 2, SINCE IT IS
WELL ESTABLISHED THAT LP'S CAN BE SOLVED IN POLYNOMIAL TIME.
Context of Revision #3
> [Bryan Olson wrote:]
> The argument for Proposition 3 cites 2.21, 2.22, 2.28, and 2.29
> as if they held for y' (the final "adjusted y"). The latter two
> are not directly constraints, but are proven assuming other
> constraints on y.
OK, I understand your argument. May (be) I need to be more detailed in
the
proof. I will do so in a (minor) revision that will be posted shortly.
moustap...@business.uconn.edu
tc...@lsa.umich.edu wrote:
> I know a couple of these professors pretty well (though maybe not the
> "old" ones), in particular Dimitris Bertsimas, Michel Goemans, and
> (less well) John Tsitsiklis.
I meant "old" in the sense of "former."
moustap...@business.uconn.edu
tc...@lsa.umich.edu wrote:
> In article <1125775523....@z14g2000cwz.googlegroups.com>,
> <moustap...@business.uconn.edu> wrote:
> >If you don't believe me on this, then ask one of old professors at MIT who
> >specializes in Math Programming.
>
A friend of mine called to my attention that my first response to Dr.
Chow had a very bad typo in it. Indeed, instead of "ask one of old
professors at MIT..." what I intended to write is "ask one of *your*
old professors at MIT..." in the sense of "ask one of your former
professors..."
To be sure, I hold all my colleagues at MIT in the highest regard. Each
of them that I know of has earned his standing as a pillar of the
profession, and the ones who are senior to me in the profession in
particular, have always been (and continue to be) models for me.
So this is simply the case of a very unfortunate typo.
Bryan Olson
> To set the record straight: my paper has gone through some revisions
> since I first posted it about a year ago. Each revision that was
> undertaken in response to a discussion in this newsgroup was undertaken
> in reponse to a suggestion that more clarification would be helpful.
> The timing of some of these coincided with revisions that were in the
> process, in response to inquiries from the Associate Editor handling
> the refereeing process of the paper. None of the revisions was the
> result of "refutation" by anyone (including people in this newsgroup),
> as you can see from the brief summary below:
Well, that's arguable, to say the least. Certainly no one has
refuting it to the point of showing that its conclusion is
false.
The last version to which I responded failed to prove what it
claimed to prove. It relied upon conditions that did not hold.
[...]
>>[Bryan Olson wrote:]
>>The argument for Proposition 3 cites 2.21, 2.22, 2.28, and 2.29
>>as if they held for y' (the final "adjusted y"). The latter two
>>are not directly constraints, but are proven assuming other
>>constraints on y.
>
> OK, I understand your argument. May (be) I need to be more detailed in
> the
> proof. I will do so in a (minor) revision that will be posted shortly.
No minor revision that corrected the error ever appeared. The
version available now makes some claims in the domain of linear
programming that I am not competent to judge. Previous versions
simply claimed a reduction to linear programming, so all that
readers needed to know about linear programming wass that it is
polynomial time. Alas, the reduction was in error.
--
--Bryan
moustap...@business.uconn.edu
> Well, that's arguable, to say the least. Certainly no one has
> refuting it to the point of showing that its conclusion is
> false.
>
> The last version to which I responded failed to prove what it
> claimed to prove. It relied upon conditions that did not hold.
>
The proof in question was actually correct. But perhaps, it needed to
be more detailed as I stated in my reply to you then. But, it is clear
that you jumped to conclusions by equating my statement "I understand
your argument" with "I agree with your argument." But those are two
different statements.
I had considered the point you made when I was writing the proof in
question, and had decided the level of detail in it had been
sufficient. So, when you made the point, I took that as an indication
that I might have had misjudged the appropriateness of the level of
detail. That is why I responded to you the way I did, in the spirit of
being constructive (instead of argumentative).
> No minor revision that corrected the error ever appeared.
The minor point I was planning to include in the paper is that if you
subtract balance flows from other balanced flows, the resulting flows
must remain balanced. That flows could not become negative as a result
of the procedure I had in the proof because each component that would
have been subtracted as suggested in the proof would have needed to be
appropriately "traced" through the network using the z-variables, as I
had suggested to you in one of our previous communications through this
newsgroup. But, I felt it was pointless to spend time arguing this
online, since I had decided I was going to include more details in the
proof itself.
> version available now makes some claims in the domain of linear
> programming that I am not competent to judge. Previous versions
> simply claimed a reduction to linear programming, so all that
> readers needed to know about linear programming wass that it is
> polynomial time. Alas, the reduction was in error.
In the process of including more details in the proof in question as
discussed above, I decided it would be better altogether, to be as
thorough as possible. So, I took a more direct, "brute-force" route
(so to speak).
There is absolutely no new claim about linear programming in the paper,
since you started posting on it. The essence of paper has remained
exactly the same. The only difference is the level of detail. I am
sorry if you feel that because of this, the work is now beyond your
ability to judge it.
Bryan Olson
> Bryan Olson wrote:
>>Well, that's arguable, to say the least. Certainly no one has
>>refuting it to the point of showing that its conclusion is
>>false.
>>
>>The last version to which I responded failed to prove what it
>>claimed to prove. It relied upon conditions that did not hold.
>
> The proof in question was actually correct. But perhaps, it needed to
> be more detailed as I stated in my reply to you then. But, it is clear
> that you jumped to conclusions by equating my statement "I understand
> your argument" with "I agree with your argument." But those are two
> different statements.
Whether or not you equate the statements, the reliance of the
proof on properties that do not hold for the objects in
question, means that it is incorrect.
> The minor point I was planning to include in the paper is that if you
> subtract balance flows from other balanced flows, the resulting flows
> must remain balanced.
Alas, that doesn't work. "Flows" are not well defined. If we
think of flows simply as paths from source to sink, that's not
strong enough to solve TSP. If we think of flows as also
distinguishing the commodity flowing on the path, then the
constraints are not strong enough to uniquely identify a set of
flows.
> That flows could not become negative as a result
> of the procedure I had in the proof because each component that would
> have been subtracted as suggested in the proof would have needed to be
> appropriately "traced" through the network using the z-variables, as I
> had suggested to you in one of our previous communications through this
> newsgroup.
And I explained why that does not work. The "tracing" is
ambiguous, because more than one set of distinguishable flows on
c.a.s.s. path can satisfy the contraints. I wrote:
There are M! c.a.s.s. paths. Any set of (non-negative) flows
on those paths, such that the total flow is one, forms
exactly one feasible solution. We have M! - 1 degrees of
freedom in creating a legal set of c.a.s.s. path flows. A
feasible solution gives us only polynomial many (order
M**14) equations, so we cannot in general solve for M!
unknowns. There just isn't enough information in a feasible
solution.
The number-of-unknowns argument proves that the recursive
retrieval cannot, in general, reconstruct the set of
c.a.s.s. path flows (even assuming the feasible solution is
a set of c.a.s.s. path flows). Intuitively, where it fails
is that the feasible solution doesn't distinguish each
c.a.s.s. path as its own commodity.
I may have been off on the number of constraints being order
M**14, but many as there are, it's polynomial. There is no way
to distinguish a unique solution for M!-1 unknowns with
polynomially-many linear equations.
--
--Bryan
moustap...@business.uconn.edu
We are running around in circles, and I definitely don't have the time.
It is all out there in the current version of the paper for you.
Unfortunatunately, it is my fault that that version has is over your
head, at a level beyond your abilities to judge, as you said yourself.
Given this, your non-sensical opinions do not really matter, and I
cannot see any in continue these fruitless discussions. Sorry.
>
> --
> --Bryan
moustap...@business.uconn.edu
Corrected text:
moustap...@business.uconn.edu wrote:
>
> We are running around in circles, and I definitely don't have the time.
> It is all out there in the current version of the paper for you.
> Unfortunately, it is *not* my fault that that version is over your
> head, at a level beyond your abilities to judge, as you say yourself.
> Given this, your non-sensical opinions do not really matter, and I
> cannot see any *benefit* in continuing these fruitless discussions. Sorry.
>