  Using methods and ideas from statistical mechanics, we propose a simple
method for obtaining rigorous upper bounds for satisfiability transition in
random boolean expressions composed of N variables and M clauses with K
variables per clause. Determining the location of satisfiability threshold
$\alpha_c=M/N$ for a number of difficult combinatorial problems is a major open
problem in the theory of random graphs. The method is based on identification
of the core -- a subexpression (subgraph) that has the same satisfiability
properties as the original expression. We formulate self-consistency equations
that determine macroscopic parameters of the core and compute an improved
annealing bound. We illustrate the method for three sample problems: K-XOR-SAT,
K-SAT and positive 1-in-K-SAT.
