The complexity of unions of disjoint sets

摘要

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.Moreover, we approach the main question in a more general way: We analyze the scope of the complexity of unions of m-equivalent disjoint sets. Under the hypothesis that NE≠coNE, we construct degrees in NP where our main question has a positive answer, i.e., these degrees are closed under unions of disjoint sets.