Abstract: We consider Boolean formulas with three literals per clause,
or 3-SAT formulas. For random formulas 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: Random Intersection Graphs, Gn,m,p, is a class of random graphs introduced in Karoński (1999) [7] where each of the n vertices chooses independently a random subset of a universal set of m elements. Each element of the universal sets is chosen independently by some vertex with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m=left ceilingn{\'a}right ceiling, for any real {\'a} different than one, we establish here, for the first time, a sharpthreshold for the graph property “Contains a Hamilton cycle”. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection graph model.
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: Today we are experiencing a major reconsideration of the computing
paradigm, as witnessed by the abundance and increasing frequency
of use of terms such as {\em ambient intelligence}, {\em ubiquitous computing}, {\em disappearing computer}, {\em grid
computer}, {\em global computing} and {\em mobile ad-hoc
networks}. Systems that can be described with such terms are of a
dynamic, with no clear physical boundary, nature and it seems that
it is impossible (or, at least, difficult) to define sharply a
number of important properties holding with certainty as well as
holding throughout the whole lifetime of the system.
%
One such system property, which is important for the viability of
a system, is {\em trust}. Our departure point is the assumption
that it seems very difficult to define static system properties
related to trust and expect that they hold eternally in the
rapidly changing systems falling under the new computing paradigm.
One should, rather, attempt to define trust in terms of properties
that hold with some limiting probability as the the system grows
and try to establish conditions that ensure that ``good''
properties hold {\em almost certainly}. Based on this viewpoint,
in this paper we provide a new framework for defining trust
through formally definable properties that hold, almost certainly,
in the limit in randomly growing combinatorial structures that
model ``shapeless'' computing systems (e.g. ad-hoc networks),
drawing on results that establish the threshold behavior of
predicates written in the first and second order logic.