FO (complexity)

From Wikipedia, the free encyclopedia

This article may require cleanup to meet Wikipedia's quality standards.
Please discuss this issue on the talk page or replace this tag with a more specific message. This article has been tagged since October 2006.
This article or section does not cite its references or sources.
Please help improve this article by introducing appropriate citations. (help, get involved!) This article has been tagged since October 2006.

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 AC0, the first class in the AC hierarchy.

Retrieved from "http://en.wikipedia.org../../../f/o/_/FO_%28complexity%29_bdd2.html"