Computer Science

Complements of multivalued functions

Document Type

Conference Paper

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 NPMVNP. 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 cone in coNPMV, which leads us to a comparison of NPMV and coNPMV with Krentel's classes Max P and Min P. 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.

Publication Title

Proceedings of the Annual IEEE Conference on Computational Complexity

Publication Date

1996

First Page

260

Last Page

269

ISSN

1093-0159

DOI

10.1109/CCC.1996.507688

Keywords

polynomials, computer science, postal services, mathematics, scholarships

APA Citation

Fenner, S., Green, F., Homer, S., Selman, A. L., Thierauf, T., & Vollmer, H. (1996). Complements of multivalued functions (pp. 260-269). IEEE.

Link to Full Text

Share

COinS