🚀 go-pugleaf

>Newsgroups: comp.theory
>Path: gene.fwi.uva.nl!fwi.uva.nl!sun4nl!mcsun!uunet!zaphod.mps.ohio-state.edu!uwm.edu!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watserv1!phonon.uwaterloo.ca!nrswart
>From: nrswart@phonon.uwaterloo.ca (Nicholas R. Swart)
>Subject: S. Gismondi and E.R. Swart's research reports.....
>Message-ID: <ByJIsL.B4y@watserv1.uwaterloo.ca>
>Sender: news@watserv1.uwaterloo.ca
>Organization: University of Waterloo
>Date: Mon, 30 Nov 1992 17:48:20 GMT
>Lines: 20

[a few lines omitted]

>So far things are looking very good. In an earlier post someone said they
>would put $10,000 down that the proof is correct. I'll raise that to
>$50,000.
>
>Nicholas Swart
>Dept. of Elec. and Comp. Engineering
>University of Waterloo
>Waterloo, Ontario
>CANADA
>N2L 3G1
>
>

If this offer has not been withdrawn yet, I hereby accept.

The ways in which the proof is incorrect are at least three. Of course
only one step needs to be incorrect for the whole proof to be incorrect.

1. The isomorphism paper relies on a claim that "Every solution to formulation
F3 can be represented by an expression of the form"
t = \sum \alpha _i q_i;
no proof of this claim is made and the authors do not know a proof.

2. The main theorem of the isomorphism paper is not merely unproven
but invalid. I have already posted a counterexample to comp.theory.

3. The "N=1" paper's claim for solution of NP-Complete problems would
not follow even if the theorem of the isomorphism paper were correct.
In detail corollary 1 of the isomorphism paper (which would be valid
if the theorem were valid) relies on the fact that if Ta=b and T has nonzero
entries wherever Q does (and T has no negative entries), Qa has nonzero
entries which are a subset of the nonzero entries of Ta (i.e. of b)
and so, since Qa has the same number of nonzero entries as b, it follows that
Qa=b.
In the claimed proofs of linear programming formulations of NP-Complete
problems in the "N=1" paper, there is no such argument possible, since
we have merely a condition that Ta= some matrix with specified values
in a subset of its entries; this is not sufficient to prove Qa= another
such matrix.

Deficiency 1 in the proof can perhaps be fixed (I believe the assertion
is probably valid but I can't prove it). Deficiency 3 can possibly be
overcome by a completely new argument (I doubt it). Deficiency 2 is fatal.
I do not know that the algorithm is incorrect but the proof definitely is.


You can send the cheque to

Dr J. M. Robson,
Department of Computer Science,
Australian National University,
GPO Box 4,
Canberra, ACT 2601,
Australia.