  We consider the K-satisfiability problem on a regular d-ary rooted tree. For
this model, we demonstrate how we can calculate in closed form, the moments of
the total number of solutions as a function of d and K, where the average is
over all realizations, for a fixed assignment of the surface variables. We find
that different moments pick out different 'critical' values of d, below which
they diverge as the total number of variables on the tree goes to infinity and
above which they decay. We show that K-SAT on the random graph also behaves
similarly. We also calculate exactly the fraction of instances that have
solutions for all K. On the tree, this quantity decays to 0 (as the number of
variables increases) for any d>1. However the recursion relations for this
quantity have a non-trivial fixed-point solution which indicates the existence
of a different transition in the interior of an infinite rooted tree.
