  Hairpin completion, derived from the hairpin formation observed in DNA
biochemistry, is an operation applied to strings, particularly useful in DNA
computing. Conceptually, a right hairpin completion operation transforms a
string $S$ into $S\cdot S'$ where $S'$ is the reverse complement of a prefix of
$S$. Similarly, a left hairpin completion operation transforms a string $S$
into $S'\cdot S$ where $S'$ is the reverse complement of a suffix of $S$. The
hairpin completion distance from $S$ to $T$ is the minimum number of hairpin
completion operations needed to transform $S$ into $T$. Recently Boneh et al.
showed an $O(n^2)$ time algorithm for finding the hairpin completion distance
between two strings of length at most $n$. In this paper we show that for any
$\varepsilon>0$ there is no $O(n^{2-\varepsilon})$-time algorithm for the
hairpin completion distance problem unless the Strong Exponential Time
Hypothesis (SETH) is false. Thus, under SETH, the time complexity of the
hairpin completion distance problem is quadratic, up to sub-polynomial factors.
