Descriptive Complexity: Fagin's Theorem, Logic, and an Alternative to Turing MachinesAn exploration of descriptive complexity—where computational classes are characterized by logical definability—and Fagin's theorem that NP equals existential second-order logic.
