The breakpoint distance between two $n$-permutations is the number
of pairs that appear consecutively in one but not in the other. In
the median problem for breakpoints one is given a set of
permutations and has to construct a permutation that minimizes the
sum of breakpoint distances to all the original ones. Recently, the
problem was suggested as a model for determining the evolutionary
history of several species based on their gene orders. We show
that the problem is already NP-hard for three permutations, and
that this result holds both for signed and for unsigned
permutations.