Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!icdoc!syma!richardh
From: richardh@syma.sussex.ac.uk (Richard John Hall)
Newsgroups: comp.theory
Subject: generating 3sat of known difficulty
Keywords: satisfiability, complexity, np
Message-ID: <3509@syma.sussex.ac.uk>
Date: 25 Sep 90 12:22:11 GMT
Organization: University of Sussex
Lines: 11

In order to test some probabilistic approaches to handling 3SAT
problems I require a simple means of generating sample 3tuple sets
of known (or at least relative) 'difficulty' ie how many
complete solutions exist, and if possible measures of
number of near-complete partial solutions.

Any suggestions, particularly if derived from real-world
applications, would be welcomed.


Richard J. Hall