Date: 19 Sep 1997 08:13:58 GMT
From: jhayward@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@imsa.edu) and especially Ryan Pierce
(rpierce@imsa.edu) for an excellent parser function.
Jonathan Hayward jhayward@math.uiuc.edu jhayward@ncsa.uiuc.edu
------------------------------
-- Brian Tao (BT300, taob@netcom.ca) "Though this be madness, yet there is method in't"