Fagin's theorem
id:
fagin-s-theorem-272-12685134
title:
Fagin's theorem
text:
Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithms for solving those problems.
The theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It was proven by Ronald Fagin in 1973 in his doctoral thesis, and appears in his 1974 pa
brand slug:
wiki
category slug:
encyclopedia
description:
Set of all properties in existential 2nd order logic is the complexity class NP
original url:
https://en.wikipedia.org/wiki/Fagin%27s_theorem
date created:
date modified:
2024-04-01T05:41:56Z
main entity:
{"identifier":"Q2226670","url":"https://www.wikidata.org/entity/Q2226670"}
image:
fields total:
13
integrity:
14