The Complexity of Some Complementation Problems

David A. Plaisted , Gregory Kucherov (1)

1 POLKA - Polynomials, Combinatorics, Arithmetic

We study the computational complexity of the problem of computing a complement representation for a set of terms. Depending on the class of sets considered, some sets are shown to have an exponential complement representation in the worst case, and some are shown to have a polynomial one. The complexity of deciding if a set has an empty complement is also studied.

Mots clés: term; ground term; ground instance; complement representation; computational complexity

Domaines: Autre [cs.OH]

David A. Plaisted, Gregory Kucherov. The Complexity of Some Complementation Problems. [Research Report] RR-3681, INRIA. 1999, pp.15. ⟨inria-00072990⟩