2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/231225Head-elementary-set-free programs were proposed in (Gebser et al. 2007) and shown to generalize over head-cycle-free programs while retaining their nice properties. It was left as an open problem in (Gebser et al. 2007) to establish the complexity of identifying head-elementary-set-free programs. This note solves the open problem, by showing that the problem is complete for co-NP.11 pages. To appear in Theory and Practice of Logic Programming (TPLP)Logic in Computer ScienceComputational ComplexityF.3.1text