A Note on the Hardness of the Critical Tuple Problem

The notion of critical tuple was introduced by Miklau and Suciu (Gerome Miklau and Dan Suciu. A formal analysis of information disclosure in data exchange. J. Comput. Syst. Sci., 73(3):507-534, 2007), who also claimed that the problem of checking whether a tuple is non-critical is complete for the second level of the polynomial hierarchy. Kostylev identified an error in the 12-page-long hardness proof. It turns out that the issue is rather fundamental: the proof can be adapted to show hardness of a relative variant of tuple-non-criticality, but we have neither been able to prove the original claim nor found an algorithm for it of lower complexity. In this note we state formally the relative variant and present an alternative, simplified proof of its hardness; we also give an NP-hardness proof for the original problem, the best lower bound we have been able to show. Hence, the precise complexity of the original critical tuple problem remains open.