ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-069 | 11th May 2006 00:00

The Complexity of Unions of Disjoint Sets

RSS-Feed




TR06-069
Authors: Christian Gla├čer, Alan L. Selman, Stephen Travers, Klaus W. Wagner
Publication: 31st May 2006 17:51
Downloads: 517
Keywords: 


Abstract:

This paper is motivated by the open question
whether the union of two disjoint NP-complete sets always is
NP-complete. We discover that such unions retain
much of the complexity of their single components. More precisely,
they are complete with respect to more general reducibilities.



ISSN 1433-8092 | Imprint