Complexity of some complementation problems

David A. Plaisted, Gregory Kucherov

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)159-165
Number of pages7
JournalInformation Processing Letters
Issue number3
Publication statusPublished - 27 Aug 1999
Externally publishedYes


Dive into the research topics of 'Complexity of some complementation problems'. Together they form a unique fingerprint.

Cite this