Abstract: We consider the performance of a number of DPLL algorithms on random 3-CNF formulas with n variables and m = rn clauses. A long series of papers analyzing so-called “myopic” DPLL algorithms has provided a sequence of lower bounds for their satisfiability threshold. Indeed, for each myopic algorithm A it is known that there exists an algorithm-specific clause-density, rA , such that if r 2.78 and the same is true for generalized unit clause for all r > 3.1. Our results imply exponential lower bounds for many other myopic algorithms for densities similarly close to the corresponding rA .
Abstract: One of the major problems algorithm designers usually face is to know in advance whether a proposed optimization algorithm is going to behave as planned, and if not, what changes are to be made to the way new solutions are examined so that the algorithm performs nicely. In this work we develop a methodology for differentiating good neighborhoods from bad ones. As a case study we consider the structure of the space of assignments for random 3-SAT formulas and we compare two neighborhoods, a simple and a more refined one that we already know the corresponding algorithm behaves extremely well. We give evidence that it is possible to tell in advance what neighborhood structure will give rise to a good search algorithm and we show how our methodology could have been used to discover some recent results on the structure of the SAT space of solutions. We use as a tool Go with the winners, an optimization heuristic that uses many particles that independently search the space of all possible solutions. By gathering statistics, we compare the combinatorial characteristics of the different neighborhoods and we show that there are certain features that make a neighborhood better than another, thus giving rise to good search algorithms.
Abstract: We consider Boolean formulas with three literals per clause,
or 3-SAT formulas. For randomformulas with m clauses over n variables,
such as r = m=n is a constant, it has been experimentally observed
that, asymptotically as r crosses the threshold value 4:2 (approximately)
the probability that {\'A} is satis¯able falls abruptly from nearly 1 to 0.
Moreover, as n increases towards larger and larger values, the transition
of the probability becomes sharper. The purpose of this paper is to simply
outline a connection between the problem of determining bounds to the
threshold value and the concept of Kolmogorov complexity.
Abstract: In this paper we present a new upper bound for randomly chosen 3-CNF formulas. In particular we show that any random formula over n variables, with a clauses-to-variables ratio of at least 4.4898 is, as n grows large, asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was 4.506. The first such bound,
independently discovered by many groups of researchers since 1983, was 5.19. Several decreasing values between 5.19 and 4.506 were published in the years between.We believe that the probabilistic techniques we use for the proof are of independent interest.
Abstract: One of the most challenging problems in probability and complexity theory is
to establish and determine the satisfiability threshold, or phase transition, for
random k-SAT instances: Boolean formulas consisting of clauses with exactly k
literals. As the previous part of the volume has explored, empirical observations
suggest that there exists a critical ratio of the number of clauses to the number
of variables, such that almost all randomly generated formulas with a higher
ratio are unsatisfiable while almost all randomly generated formulas with a lower
ratio are satisfiable. The statement that such a crossover point really exists is
called the satisfiability threshold conjecture. Experiments hint at such a direction,
but as far as theoretical work is concerned, progress has been difficult. In an
important advance, Friedgut [23] showed that the phase transition is a sharp one,
though without proving that it takes place at a “fixed” ratio for large formulas.
Otherwise, rigorous proofs have focused on providing successively better upper
and lower bounds for the value of the (conjectured) threshold. In this chapter, our
Abstract: The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable
ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up
to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. In this paper,
we consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own
right. More specifically, we show how the method of local maximum satisfying truth assignments can be combined with results for
the occupancy problem in schemes of random allocation of balls into bins in order to achieve an upper bound for the unsatisfiability
threshold less than 4.571. In order to obtain this value, we establish a bound on the q-binomial coefficients (a generalization of the
binomial coefficients). No such bound was previously known, despite the extensive literature on q-binomial coefficients. Finally,
to prove our result we had to establish certain relations among the conditional probabilities of an event in various probabilistic
models for randomformulas. It turned out that these relations were considerably harder to prove than the corresponding ones for
unconditional probabilities, which were previously known.
