#Descriptive-Complexity
1 post in tag “Descriptive-Complexity”.
Descriptive Complexity: Fagin's Theorem, Logic, and an Alternative to Turing Machines
2019-10-12An exploration of descriptive complexity—where computational classes are characterized by logical definability—and Fagin's theorem that NP equals existential second-order logic.