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

[The fuzzy one]

	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.

You have been enlightened     | "I use vi under Win!!!"
by the fuzzy one              | cs207bc at cello.it.uq.edu.au
memory at techie.com (personal)  | s335810 at cello.it.uq.edu.au

---------- Forwarded message ----------
Date: Wed, 1 Oct 1997 19:13:57 -0400
From: Brian Tao <taob at NBC.NETCOM.CA>
To: BUGTRAQ at NETSPACE.ORG
Subject: [RISKS DIGEST 19.40] Possible breakthrough in NP-completeness

------------------------------

Date: 19 Sep 1997 08:13:58 GMT
From: jhayward at students.uiuc.edu (jonathan seth hayward)
Subject: Possible breakthrough in NP-completeness

I now have what I believe to be a polynomial time solution to an NP-complete
problem (specifically, satisfying a propositional formula expressed in terms
of parentheses, variables, negations, and conjunctions).  I am posting to
security and cryptography related newsgroups because my algorithm, if
correct, may have substantial implications for cryptography and consequently
security issues (so that, if correct, the algorithm is known to security
people as soon as everybody else).

This program produces correct output for small formulas that I am able to
manually verify, and it had an execution time on a formula of 100 variables
was less than a minute.  (Compare with brute force, which (on a
supercomputer capable of 1 billion elementary operations per second) would
take longer than the age of the universe.)

I will post a uuencoded compressed tar of a directory hierarchy with the
algorithm, implemented in C and supplemented by some bourne shell scripts,
as an immediate followup to this post.  Should the binary UseNet post be
cancelled by someone like Dick Depew, it is also available (same format) on
the web at:

        http://www.imsa.edu/~jhayward/npc.tar.Z.uu
        http://www.students.uiuc.edu/~jhayward/npc.tar.Z.uu

This release should be considered a beta release, i.e., while I am
reasonably sure that the algorithm is correct, the specific implementation
may have bugs.

Thanks to David Henderson (davidh at imsa.edu) and especially Ryan Pierce
(rpierce at imsa.edu) for an excellent parser function.

Jonathan Hayward jhayward at math.uiuc.edu jhayward at ncsa.uiuc.edu

------------------------------

--
Brian Tao (BT300, taob at netcom.ca)
"Though this be madness, yet there is method in't"

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