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

tchow@xxxxxxxxxxxxx wrote: 
In article <1114713726.126023.259970@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
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.

--
Mitch Harris
(remove q to reply)

.