TR#:  CS0819 
Class:  CS 
Title:  ON AVERAGE CASE COMPLEXITY OF SAT FOR
SYMMETRIC DISTRIBUTIONS. 
Authors:  J.A. Makowsky and A. Sharell 
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 averagecase complexity of NPcomplete 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 averagecase 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 kCNF (sets of kliteralclauses), 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 polynomialtime, noerror [38,19]) randomized reductions are appropriate in averagecase complexity. We also observe, that there are nonflat 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/cgibin/trinfo.cgi/1994/CS/CS0819), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1994
To the main CS technical reports page