Teorema de Fagin é um resultado da teoria da complexidade descritiva, que afirma que o conjunto de todas as propriedades que podem ser expressas na lógica de segunda ordem existencial, é precisamente a classe de complexidade NP. É notável, pois é uma caracterização da classe NP que não invoca um modelo de computação, tal como uma máquina de Turing. Wikipedia