Technical Report CS0819

TR#:CS0819
Class:CS
Title: ON AVERAGE CASE COMPLEXITY OF SAT FOR SYMMETRIC DISTRIBUTIONS.
Authors: J.A. Makowsky and A. Sharell
PDFCS0819.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.

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

To the list of the CS technical reports of 1994
To the main CS technical reports page

Computer science department, Technion
admin