# Technical Report CS0819

 TR#: CS0819 Class: CS Title: ON AVERAGE CASE COMPLEXITY OF SAT FOR SYMMETRIC DISTRIBUTIONS. Authors: J.A. Makowsky and A. Sharell PDF CS0819.pdf Abstract: We investigate in this paper natural' distributions for the satisfiability problem (SAT) of propositional logic, using concepts introduced by [25,19,1] to study the average-case complexity of NP-complete problems. Gurevich showed that a problem with a flat distribution is not DistNP complete (for deterministic reductions), unless DEXTPTime \Neq NEXPTime. We express the known results concerning fixed size and fixed density distributions for CNF in the framework of average-case complexity and show that all these distributions are flat. We introduce the family of symmetric distributions, which generalizes those mentioned before, and show that bounded symmetric distributions on ordered tuples of clauses (CNFTuples) and on k-CNF (sets of k-literal-clauses), are flat. This eliminates all these distributions as candidates for provably hard' (i.e., DistNP complete) distributions for SAT, if one considers only deterministic reductions. Given the (presumed) naturalness and generality of these distributions, this result supports evidence that (at least polynomial-time, no-error [38,19]) randomized reductions are appropriate in average-case complexity. We also observe, that there are non-flat distributions for which SAT is polynomial on the average, but that this is due to the particular choice of the size functions. Finally, Chv\'{a}tal and Szemer\'{e}di ([8]) have shown that for certain fixed size distributions (which are also flat) resolution is exponential for almost all instances. We use this to show that every resolution algorithm will need at least \exp(n^{\alpha}) (for any 0 < \alpha < 1) time on the average. In other words, resolution based algorithms will not establish that SAT, with these distributions, is in AverP. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1994/CS/CS0819), rather than to the URL of the PDF files directly. The latter URLs may change without notice.