FO (complexity)

From Wikipedia, the free encyclopedia

This article may require cleanup to meet Wikipedia's quality standards. Please improve this article if you can. (October 2006)

This article does not cite any references or sources. (October 2006) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In descriptive complexity theory, FO is the complexity class of all languages which can be specified using first-order logic. Adding the BIT predicate results in the class FO+BIT. In circuit complexity, FO can be shown to be equal to AC⁰, the first class in the AC hierarchy.