Re: P=NP: Linear Programming Formulation of the TSP

tchow@xxxxxxxxxxxxx wrote:
Mitch Harris <harrisq@xxxxxxxxxxxxxxxxxxxxx> wrote:
tchow@xxxxxxxxxxxxx wrote: 
Jennifer Anderson <jen_ander_son@xxxxxxxxx> wrote:

Why don't they just use computers to check if it's right? 

Computers will at most be able to check that the formulation performs
correctly in a finite number of cases.  This won't *prove* that P = NP.

You don't know that! 

For that, the argument that this works in general has to be checked for
logical correctness.  And the world is not quite at the stage yet where
it is routine to write mathematical proofs of nontrivial theorems in
machine-checkable form.

"nontrivial" means no known algorithm. When there is a proven correct algorithm for a class of problems, those problems then become trivial.

I suspect we're talking at cross-purposes here. 

Oh sure, I was just trying to draw you out into what you really think.

Jennifer Anderson appears to be suggesting that by implementing Diaby's
LP and running it on selected examples, we can verify whether the LP
is correct.

I took her question to be relevant to the more immediate discussion about reviewing papers, peer review, and such, not about the specific linear programming method. But now I see that your answer was about the OPs LP ideas.

--
Mitch Harris
(remove q to reply)

.

Relevant Pages

  • Re: return in loop for ?
    ... there is a single program which can verify itself. ... the Halting Problem is just a sub-set of the verification ... proving formal correctness, since you aren't concerned whether your ...
    (comp.lang.python)
  • Re: Hardware
    ... Besides, OP will still need to verify the answer's correctness, requiring additional research, as any question here can illicit all sorts of responses. ... So, simply asking a question in a highly opinionated, peer to peer group may actually require more work on the asker's part if they are hoping to get a good grade as the person responding may know even less than the person asking the question. ...
    (microsoft.public.windows.vista.hardware_devices)
  • A connection between electron charge and certain cosmological parameters
    ... A high school student can ... verify the correctness of the equation by substituting the accepted ... the values of the cosmological parameters used. ...
    (sci.physics)
  • Re: Coherent exposition of OO?
    ... but there's no reason to verify their correctness. ... Art is an ... entirely subjective medium; software isn't. ...
    (comp.object)
  • Question about OMAC
    ... How do you verify the MAC for correctness? ... Tom ...
    (sci.crypt)