The complexity of some complementation problems

Authors
Plaisted, DA Kucherov, G
Citation
Da. Plaisted et G. Kucherov, The complexity of some complementation problems, INF PROCESS, 71(3-4), 1999, pp. 159-165
Citations number
21
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
71
Issue
3-4
Year of publication
1999
Pages
159 - 165
Database
ISI
SICI code
0020-0190(19990827)71:3-4<159:TCOSCP>2.0.ZU;2-K
Abstract
We study the computational complexity of the problem of computing a complem ent representation for a set of terms. Depending on the class of sets consi dered, some sets are shown to have an exponential complement representation in the worst case, and some are shown to have a polynomial one. The comple xity of deciding if a set has an empty complement is also studied. (C) 1999 Elsevier Science B.V. All nights reserved.