Fagin's theorem, Turing Machines and Quantum computing
Fagin's theorem stands as one of the foundational results within
descriptive complexity theory, a discipline nestled within
computational complexity theory. Unlike traditional approaches relying
on algorithmic behaviors, descriptive complexity theory characterizes
complexity classes through logic-based formulations of problem
properties. At its core, the theorem asserts that the collection of
properties expressible through existential second-order logic
corresponds precisely to the complexity class NP. This theorem not
only illuminates the relationship between logic and computational
complexity but also provides a pivotal bridge between the two realms.
Yiannis Kiouvrekis
Last modified: Wed Mar 20 2024