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.