In ABox abduction, we are given a knowledge base together with an
ABox—the observation—that is not logically entailed by the knowledge base,
and are looking for another ABox—the hypothesis—that, when added to the
knowledge base, would make the observation entailed. This has applications in
explaining negative entailments and missing query answers, as well as in diag-
nosis. To get useful hypotheses, in signature-based abduction, we additionally
provide a signature of abducible names, and require the hypothesis to use only
names from that signature. In the variant we are considering, the hypothesis may
otherwise use fresh individual names, as well as complex concepts constructed
in arbitrary way using the names in the signature. It was recently shown that this
variant of abduction is in N2EXPTIME^NP , and that hypotheses may require con-
cepts that are of triple exponential size. We complement those results by showing
a matching N2EXPTIME^NP lower bound, and show that in the worst case, hy-
potheses may also use a double exponential number of fresh individual names.