Re: Hofman and Diaby talk about P=NP at INFORMS 2007



On Feb 10, 1:22 pm, t...@xxxxxxxxxxxxx wrote:
In article <45c9ea9f$0$562$b45e6...@xxxxxxxxxxxxxxxxxxxxxxxxx>, I wrote:
So there are 31988850360320 variables and 14155377697 constraints.
Moews and Hofman have checked all 14155377697 constraints and have not
been able to find a violated constraint.

Professor Diaby, this is a reminder that we are still waiting for your
response. You asked us to determine how many constraints Moews and Hofman
checked, and to compare this with how many constraints they *should* have
checked. We now know that they checked 14155377697 constraints, and this
also appears to me to be the correct number of constraints that they
*should* have checked. Therefore, the simple counting procedure that you
suggested has not uncovered the violated constraint.

So I repeat: David Moews has responded promptly to your request. Will
you now respond promptly to my request, to find the violated constraint?
--
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


Dr Chow,

I am sure whatever specific statement I make now regarding this will
only lead to another round of circles, and I just don't have the time
now.

....But, for your information, I am currently working on a generalized
version of my model, and that will give me the chance to re-examine
the proofs. ...If Hofman has indeed stumbled into something thatshows
that constraints 2.12-2.13 are not redundant in my model after all, I
am confident I would uncover where the the oversight occurrs.

So, whatever the issue of this "counter-example" is, it can be
redressed trivially... Unfortunately, I just don't have the time for
this now. So, may be we can all relax a little about this for now?

//MD


.



Relevant Pages

  • Re: P=NP: Linear Programming Formulation of the TSP
    ... > I believe I understand what Dr. Moews is trying to do perfectly. ... then the new polytope is not the same as the original one. ... >>>charaterize the original polytope in terms of these constraints as ... >>>want to identify and discard redundent variables and constraints ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... I believe I understand what Dr. Moews is trying to do perfectly. ... >>Either the constraints developed by Moews using his xvariables ... then the new polytope is not the same as the original one. ... then they are redundent with respect to the original ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... Dr. Moews: I am busy with exams, grading, etc. at this time. ... That is clearly not what Yannakakis says. ... Either the constraints developed by Moews using his xvariables ... then the new polytope is not the same as the original one. ...
    (comp.theory)
  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... You asked us to determine how many constraints Moews and Hofman ... suggested has not uncovered the violated constraint. ...
    (comp.theory)
  • A reply to Moews on Diaby contradicting Yannakakis
    ... A Response to Moews on: ... it is ALWAYS possible to add any number of redundent variables ... Either the constraints developed by Moews using his xvariables ... then the new polytope is not the same as the original one. ...
    (comp.theory)