[RISKS DIGEST 19.40] Possible breakthrough in NP-completeness

[taob () NBC NETCOM CA (Brian Tao)]

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

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"