P (complexity) - Alternative Characterizations

Alternative Characterizations

In descriptive complexity, P can be described as the problems expressible in FO (LFP), the class of first-order logic with a least fixed point operator added to it. In Immerman's 1999 textbook on descriptive complexity, Immerman ascribes this result to Vardi and to Immerman.

Read more about this topic:  P (complexity)

Famous quotes containing the word alternative:

    Education must, then, be not only a transmission of culture but also a provider of alternative views of the world and a strengthener of the will to explore them.
    Jerome S. Bruner (20th century)