CJTCS Volume 1999 Article 3

Complements of Multivalued Functions

Stephen Fenner (University of Southern Maine), Frederic Green (Clark University), Steven Homer (Boston University), Alan L. Selman (SUNY at Buffalo), Thomas Thierauf (Universität Ulm), and Heribert Vollmer (Universität Würzburg)
19 March 1999
Abstract

We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV, this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it is essentially the same as that of NPMV^NP. Complete functions for coNPMV are exhibited and central complexity-theoretic properties of this class are studied. We show that computing maximum satisfying assignments can be done in coNPMV, which leads us to a comparison of NPMV and coNPMV with Krentel's classes MaxP and MinP. The difference hierarchy for NPMV is related to the query hierarchy for coNPMV. Finally, we examine a functional analogue of Chang and Kadin's relationship between a collapse of the Boolean hierarchy over NP and a collapse of the polynomial-time hierarchy.

The LaTeX source and DVI are disabled temporarily while we check for a problem in formatting. PostScript and PDF are available below.

[] Article 2
[back] Volume 1999 [back] Published articles
[CJCTS home]

Last modified: Sat Mar 20 09:32:31 CST 1999