COMPLEXITY OF UNIVERSAL CIRCUMSCRIPTION
Alexei Lisitsa · International Journal of Foundations of Computer Science · 1993
The computational problem of model checking for circumscription of first-order formulae is studied. It is shown that there is a universal first-order formula whose circumscription has coNP-complete model checking problem. This answers a question raised by P.H. Kolaitis and C.H. Papadimitriou.