The Complexity of Unions of Disjoint Sets Christian Glaßer∗, Alan L. Selman†, Stephen Travers‡, and Klaus W. Wagner∗ Abstract This paper is motivated by the open question whether the union of two disjoint NPcomp - Disjoint sets - Document - PDFSEARCH.IO

First Page	Meta Content
	The Complexity of Unions of Disjoint Sets Christian Glaßer∗, Alan L. Selman†, Stephen Travers‡, and Klaus W. Wagner∗ Abstract This paper is motivated by the open question whether the union of two disjoint NPcomp Add to Reading List Document Date: 2006-11-08 15:58:52 Open Document File Size: 228,08 KB Share Result on Facebook Company Preliminaries We / / Country Germany / United States / / / Event Person Communication and Meetings / / Facility University of W¨ / / Organization University of W¨ / National Science Foundation / Department of Computer Science / Disjoint Sets Whose Union / / Person Alan L. Selman / Stephen Travers / Ai / / Position author / ≡pm / E≡pm / Prime Minister / A≤pm / 0A ≡pm / C≤pm / / ProgrammingLanguage FP / / Technology cryptography / simulation / / SocialTag Complexity classes Computability theory NP-complete problems Structural complexity theory Polynomial hierarchy NP PP Many-one reduction Oracle machine Theoretical computer science

The Complexity of Unions of Disjoint Sets Christian Glaßer∗, Alan L. Selman†, Stephen Travers‡, and Klaus W. Wagner∗ Abstract This paper is motivated by the open question whether the union of two disjoint NPcompAdd to Reading List