  In logics with the Craig interpolation property (CIP) the existence of an
interpolant for an implication follows from the validity of the implication. In
logics with the projective Beth definability property (PBDP), the existence of
an explicit definition of a relation follows from the validity of a formula
expressing its implicit definability. The two-variable fragment, FO2, and the
guarded fragment, GF, of first-order logic both fail to have the CIP and the
PBDP. We show that nevertheless in both fragments the existence of interpolants
and explicit definitions is decidable. In GF, both problems are
3ExpTime-complete in general, and 2ExpTime-complete if the arity of relation
symbols is bounded by a constant c not smaller than 3. In FO2, we prove a
coN2ExpTime upper bound and a 2ExpTime lower bound for both problems. Thus,
both for GF and FO2 existence of interpolants and explicit definitions are
decidable but harder than validity (in case of FO2 under standard complexity
assumptions).
