  We discuss the time complexity of the word and conjugacy search problems for
free products $G = A \star_C B$ of groups $A$ and $B$ with amalgamation over a
subgroup $C$. We stratify the set of elements of $G$ with respect to the
complexity of the word and conjugacy problems and show that for the generic
stratum the conjugacy search problem is decidable under some reasonable
assumptions about groups $A,B,C$.
