Fagin-Theorem

• Descriptive Complexity: Fagin's Theorem, Logic, and an Alternative to Turing Machines · 2019-10-12

  An exploration of descriptive complexity—where computational classes are characterized by logical definability—and Fagin's theorem that NP equals existential second-order logic.