  As well known, weak K4 and the difference logic DL do not enjoy the Craig
interpolation property. Our concern here is the problem of deciding whether any
given implication does have an interpolant in these logics. We show that the
nonexistence of an interpolant can always be witnessed by a pair of bisimilar
models of polynomial size for DL and of triple-exponential size for weak K4,
and so the interpolant existence problems for these logics are decidable in
coNP and coN3ExpTime, respectively. We also establish coNExpTime-hardness of
this problem for weak K4, which is higher than the PSpace-completeness of its
decision problem.
