Summary: 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 \(co\)NP, D\(^p\), \(\Pi^P_2\), FP\(^{\text{NP}}_|\), FNP\(/Opt\text{P}[\log n]\) and FP\(_|^{\Sigma^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\(//Opt\text{P}[\log n]\), solving an open question by C. H. Papadimitriou [Proceedings of the 32nd IEEE Symposium on the Foundations of Computer Science 1991, 163-169].