 Fagin's theorem

Fagin's theorem is a fundamental result in the field of computational complexity theory, particularly concerning the classification of decision problems that can be expressed in terms of a certain type of logical formulas. Specifically, it characterizes the complexity of certain types of queries in databases. The theorem states that a decision problem is in the complexity class NP if and only if it can be expressed as a first-order logic formula with a quantifier prefix that allows for a fixed number of alternating quantifiers.