  We show that two important problems that have applications in computational
biology are ASP-complete, which implies that, given a solution to a problem, it
is NP-complete to decide if another solution exists. We show first that a
variation of Betweenness, which is the underlying problem of questions related
to radiation hybrid mapping, is ASP-complete. Subsequently, we use that result
to show that Quartet Compatibility, a fundamental problem in phylogenetics that
asks whether a set of quartets can be represented by a parent tree, is also
ASP-complete. The latter result shows that Steel's \sc Quartet Challenge, which
asks whether a solution to Quartet Compatibility is unique, is coNP-complete.
