[H-GEN] [RISKS DIGEST 19.40] Possible breakthrough in NP-completeness (fwd)

[Anthony Towns]

-----BEGIN PGP SIGNED MESSAGE-----

On Fri, 3 Oct 1997, The fuzzy one wrote:

> 	I thought this one was worth passing on from bugtraq, just to whet
> the appetites of anyone with enough maths to understand a word of this
> guy's algorithm.
> 	Of course it could all be a hoax, but all the files are where he
> says they are.  Someone with more knowhow than me should be looking at
> this.
> 	No replies on bugtraq yet.

There were replies on sci.math, though.

It doesn't work. 

Dan Hoey (from the American Navy's centre for AI) pointed out that his
analysis of Intersect() was incorrect -- it was exponentional rather
than O(n).

More interestingly, Chris Hall (Dimensional Communications?) notes
that the solution takes (empiracally) exponentional time for
expressions of the form:

	!(!(!...(!a^!b)^c)^!d)^e)^!f)...)

(not the second variable, leave the third, not the fourth, leave the
fifth, etc...)

(He presents an attempted solution to P=?=NP, and then asks:
	``Prof. Pitt, I trust that this algorithm, if correct, would
	qualify as material for the extra quarter credit as dealing
	with computational complexity''
 If correct, yeah, I think it might get you extra credit. And
 probably a PhD and a few honorary DSc's, too.)

Cheers,
aj



- --
Anthony Towns <aj at humbug.org.au> <http://student.uq.edu.au/~s343676/>
I don't speak for anyone save myself. PGP encrypted mail preferred.

``Like the ski resort of girls looking for husbands and husbands looking
  for girls, the situation is not as symmetrical as it might seem.''

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3ia
Charset: ascii
Comment: Key available at http://student.uq.edu.au/~s343676/aj_key.asc

iQCVAwUBNDRFsuRRvX9xctrtAQGdXwQAsSG25RAqL8szR8rMRmVse57uYKCk4UEW
5S4ni+svzTB7CVa9b6//x4F93rkZBY7N3jjmOKttujei2GjUlUF7vc0r/57xC4xm
2dgpiR1yYfFvxH0wsgij/LWwfwH24lrkjn1Z6HVF6CeXZMbEyP3ktikkBI2nfwm1
lg1u4Jj7D+s=
=Gp4d
-----END PGP SIGNATURE-----

----------------------- HUMBUG General List --------------------------------
echo "unsubscribe general" | mail majordomo at humbug.org.au # To Unsubscribe