#Fagin-Theorem

1 post in tag “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.