Bounded fitting is a general paradigm for learning logical formulas from positive and negative data examples, that has received considerable interest recently. We investigate bounded fitting for the description logic \(\mathcal {ALC} \) and its syntactic fragments. We show that the underlying size-restricted fitting problem is \(\text {NP} \) -complete for all studied fragments, even in the special case of a single positive and a single negative example. By design, bounded fitting comes with probabilistic guarantees in Valiant’s PAC learning framework. In contrast, we show that other classes of algorithms for learning \(\mathcal {ALC} \) concepts do not provide such guarantees. Finally, we present an implementation of bounded fitting in \(\mathcal {ALC}\) and its fragments based on a SAT solver. We discuss optimizations and compare our implementation to other concept learning tools.