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:
“A mental disease has swept the planet: banalization.... Presented with the alternative of love or a garbage disposal unit, young people of all countries have chosen the garbage disposal unit.”
—Ivan Chtcheglov (b. 1934)