From: mpd@netcom.com (Mike Duvos)
Date: Sat, 9 Nov 1996 12:13:37 -0800 (PST)
To: Cypherpunks@toad.com
Subject: Small "Hard" Problems Wanted
Message-ID: <199611092013.MAA23300@netcom16.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


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.                      $