Fellow C'Punks, In my quest to reduce NP-Completeness to NP-Not-So-Hard-Ness, I have just finished coding and debugging a very complicated algorithm which manages to solve circuit satisfiability problems of up to 1000 nodes in a few minutes and about half a meg of memory. It works directly from the connectivity information and the time required is not a function of the number of input bits. Circuit satisfiability problems, and other well known problems like Max P-Sat, are amongst the more useful canonically NP-Complete problems, since other problems map very nicely into them. The algorithm is currently in APL, and I am in the process of recoding it in C, after which I plan to test it on reduced round DES, full 16 round DES, and some RSA problems of various sizes. I already have C code to map RSA and n-round DES problems into an appropriate circuit satisfiability problem and generate appropriate input for the algorithm, so finishing up the C version is the only remaining step before these tests can begin. The current APL reference inplementation can still handle problems up to about 1000 nodes, which should include a lot of stuff for which exhaustive search would be intractable, even on supercomputers. Nothing I have so far fed the reference implementation has bombed it, and I would like to make sure it is perfect before the finely tuned C version is complete. So if anyone has a "hard" problem they are dying to solve, which maps into a circuit satisfiability problem that isn't over 1000 nodes, Email it to me and I will see if I can divine the answer. I will post any interesting results to the list, of course. -- Mike Duvos $ PGP 2.6 Public Key available $ mpd@netcom.com $ via Finger. $