Motivated by problems that arise in computing
<I>degrees of belief}</I>, we consider the problem of computing
asymptotic conditional probabilities for first-order sentences.  Given
first-order sentences <I>phi</I> and <I>theta</I>, we consider the
structures with domain <I>{1,...,N}</I> that satisfy <I>theta</I>,
and compute the fraction of them in which <I>phi</I> is true.  We then
consider what happens to this fraction as <I>N</I> gets large.  This
extends the work on 0-1 laws that considers the limiting probability
of first-order sentences, by considering asymptotic <I>conditional</I>
probabilities.  As shown in [Liogonkii,GHK1a], in the general case,
asymptotic conditional probabilities do not always exist, and most
questions relating to this issue are highly undecidable.  These
results, however, all depend on the assumption that <I>theta</I> can
use a nonunary predicate symbol.  Liogonkii shows that if we condition
on formulas <I>theta</I> involving unary predicate symbols only (but
no equality or constant symbols), then the asymptotic conditional
probability does exist and can be effectively computed.  This is the
case even if we place no corresponding restrictions on <I>phi</I>.  We
extend this result here to the case where <I>theta</I> involves
equality and constants.  We show that the complexity of computing the
limit depends on various factors, such as the depth of quantifier
nesting, or whether the vocabulary is finite or infinite.  We
completely characterize the complexity of the problem in the different
cases, and show related results for the associated approximation
problem. <p>