The Complexity of Selecting Maximal Solutions

Many important computational problems involve finding a maximal (with respect to set inclusion) solution in some combinatorial context. We study such maximality problems from the complexity point of view, and categorize their complexity precisely in terms of tight upper and lower bounds. Our results give characterizations of coNP, DP, ΠP 2, FPNP ||, FNP//OptP [log n] and FPΣP ||2 in terms of subclasses of maximality problems. An important consequence of our results is that finding an X-minimal satisfying truth assignment for a given CNF boolean formula is complete for FNP//OptP[log n], solving an open question by Papadimitriou [Proceedings of the 32nd IEEE Symposium on the Foundations of Computer Science, 1991, pp. 163-169].

Authors

• Z.Z. Chen
• S. Toda

Keywords

No keywords are indexed for this paper.