A particular class of Horn formulae, which we denote k-HCNF, are those represented by CNF formulae in which each clause contains at most one positive literal and depends on exactly k variables. It is obvious that any formula in k-HCNF is satisfied by any instantiation of its variables having the property that at most k-2 variables have been set to true. Where such instances arise from representations of Knowledge-based systems' rules, satisfying instantiations of this form are rather uninteresting: only the trivial conclusion that the knowledge-base is applicable if no rule is activated can be deduced. If, however, one concentrates on `non-trivial' instantiations which must have at least k-1 variables set to true, then satisfying assignments of such a form are of interest, since their existence implies that a given set of rules is consistent and with at least one rule being activated.
Using the model of random k-HCNF, Fp(n,k), in which each possible clause occurs (independently) with probability p(n,k) it is shown that:
For all (constant) k>1: for all d>0
If p(n,k)>=(k-1+d)ln(n)/n P[Fp(n,k) is `non-trivially' satisfiable] -> 0
If p(n,k)<=(k-1-d)ln(n)/n P[Fp(n,k) is `non-trivially' satisfiable] -> 1
For Computer Scientists, how particular combinatorial properties of a given structure relate to the efficiency with which other properties of the same structure can be determined, is a significant question. If one concentrates on the particular case of n-vertex graphs, G(V,E), undoubtedly the cases of most interest, are those where the graph properties considered are NP-complete - thus, regarded as unlikely to admit a generally applicable. efficient algorithmic solution. Well-known examples of such properties are 3-vertex colourability, Hamiltonian cycle, Chromatic Index, |V|/2-clique. Many of these problems have variants which occur in `practical' scenarios, and so, in the absence of guaranteed general efficient methods, it is important to identify solution approaches which can be effective under certain conditions. It is against this background that the idea of methods with efficient run-time on average developed, and has subsequently proved to be of considerable importance in the design of `special-case' efficient algorithms.
The phenomena of `phase-transition effects' discovered in early work on combinatorial graph theory, indicates that the presence or absence of a property very often depends critically on the graph density, i.e. the ratio |E|/n. Thus, by analytic means, one can establish, for example, that `almost all' graphs whose density exceeds f(n) have some specific property, e.g. for f(n)=0.5logen, almost all graphs have a Hamiltonian cycle. Exploiting such combinatorial effects poses a number of interesting challenges with respect to the design of efficient `average-case' algorithms: how can the fact that a sufficiently dense graph `almost certainly' has a given property be used to construct an `efficient on average' decision method which correctly decides if any sufficiently dense input graph has the property? where such properties are `witnessed' by the existence of a specific sub-graph (as in Hamiltonicity) can the density properties be exploited to give fast average-case algorithms not only to decide but also to find such a witness where it exists?
In this overview talk, we outline some of the background to these questions and possible avenues of attack concerning them. As an illustration, we consider the famous fast average-case method of Angluin and Valiant which provably finds Hamiltonian cycles in graphs which are sufficiently dense.
Random regular graphs make an (at least theoretically) interesting communication network because they combine low, finite degree with high expansion almost always. When these networks are very large one is faced with the issue of fault tolerance . We continue the study of the fault-tolerance properties of random regular graphs started by Spirakis et al. A faulty random regular graph is obtained by deleting each edge of a random regular graph with a given fault probability.
We show 2 results: First we determine the threshold probability for the existence of a linear sized component inside a faulty random regular graph. Second, we present sufficient conditions on the degree and the fault probability to ensure the existence of a linear sized expander inside a faulty random regular graph. We show that such an expander can be found as the 3-core (maximal subgraph with each node of degree of at least 3) of the faulty graph by a simple linear time algorithm.
We determine the asymptotical satisfiability probability of a random at-most-k-Horn formula, via a probabilistic analysis of a simple version, called PUR, of positive unit resolution. We show that for k=k(n)->oo the problem can be ``reduced'' to the case "uniform case" k(n)=n, which has been previously fully analyzed (see authors' abstract in the Proceedings of SODA'99).
On the other hand, in the case k=constant the behavior of PUR is modeled by a simple queuing chain, leading to a closed-form solution when k=2. Our analysis predicts an ``easy-hard-easy'' pattern in this latter case.
Under a rescaled parameter, the graphs of limit probability corresponding to finite values of k converge to the one for the uniform case, a critical behavior similar to the one found experimentally by Kirkpatrick and Selman for k-SAT. The phenomenon is qualitatively explained by a threshold property for the number of iterations PUR makes on random satisfiable Horn formulas.
We show that the k-SAT problem can be recast as a vertex-painting problen on a hypercube, and this leads to a Markov Chain. We then consider an example of a family of Markov chains with a spectral gap and show that it exhibits O(n) cut-off in the sense of Diaconis. We argue that this, and bandedness, is what lies at the heart of the O(n) phase transition in the k-SAT problem.
Harris and Keane (1997)1 considered the distribution $\mu\theta$ of coin tosses generated using a coin with bias $\theta$ at arrivals in a renewal process, and a fair coin at other times. We answer a question they posed, providing examples of square summable sequences of renewal probabilities $un$ with a phase transition: for $\theta$ small, $\mu\theta$ is equivalent to the distribution $\mu0$ of i.i.d. fair coins, while for $\theta$ large, $\mu0$ and $\mu\theta$ are singular. For these sequences, an unknown $\theta$ can be determined if $\theta$ is large. When ${un}$ is not square summable, the unknown bias can always be recovered.
M. Harris and M. Keane (1997). Random coin tossing. Probab. Theory Relat. Fields
109, 27-37
(This is work with Robin Pemantle and Yuval Peres)
The NP-Complete class of decision problems are simply stated tasks, for example in combinatorics, that may require enormous computing effort to solve. Heuristic methods often reach exact solutions, but fail badly at ``phase boundaries'' across which the decision to be reached changes from almost always having one value to almost always having a different value. We report an analytic solution based on concepts and tools of statistical mechanics and experimental investigations of the phase transition that occurs in K-SAT, a widely studied NP-Complete problem. We show that when the underlying computational task exhibits a smooth (continuous) phase transition, resource requirements grow only polynomially with system size, while abrupt (discontinuous) phase transitions correspond to an exponential growth in resource requirements, characteristic of truly hard computational problems. Our results show that techniques from statistical physics can provide important new insights into computational phenomena, and vice versa, that computational problems provide models which challenge the assumptions of physics.
This talk will outline some doctoral AI work in its early stages. I am intending to study empirically some properties of sets of instances sampled from the Random k-SAT model of the boolean satisfiability (SAT) problem. Particularly of interest is the question of which properties affect the cost to find a satisfiability witness via the local search technique and cause it to peak near the phase transition. It is thought that model clusters and failed clusters may play a part in this. These concepts are introduced and methods for determining them are discussed. Time permitting, I will also mention the possibility of enhancing local search so as to reduce the cost impact of these properties.
Poisson approximations for the counts of a given subgraph in large random graphs were accomplished using Stein's method by Barbour and others. Compound Poisson approximation results, on the other hand, have not appeared, at least partly because of the lack of a suitable coupling. We address that problem by introducing the concept of cluster determining pairs, leading to a useful coupling for a large class of subgraphs we call local. We find bounds on the compound Poisson approximation of counts of local subgraphs in large random graphs.