Editing P (complexity) (section)

==Alternative characterizations==
In [[descriptive complexity]], P can be described as the problems expressible in [[FO(LFP)]], the [[first-order logic]] with a [[least fixed point]] operator added to it, on ordered structures.  In Immerman's 1999 textbook on descriptive complexity,<ref>{{cite book | last = Immerman | first = Neil | author-link = Neil Immerman | title = Descriptive Complexity|title-link= Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | isbn = 978-0-387-98600-5 | page = 66}}</ref> Immerman ascribes this result to Vardi<ref>{{cite conference | last = Vardi | first = Moshe Y. | title = The Complexity of Relational Query Languages | book-title = STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing | year = 1982 | pages = 137–146 | doi = 10.1145/800070.802186}}</ref> and to Immerman.<ref>{{cite conference | last = Immerman | first = Neil | title = Relational Queries Computable in Polynomial Time | book-title = STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing | year = 1982 | pages = 147–152 | doi = 10.1145/800070.802187}}  Revised version in ''Information and Control'', 68 (1986), 86–104.</ref>

It was published in 2001 that PTIME corresponds to (positive) [[range concatenation grammars]].<ref name="Kallmeyer2010">{{cite book|author=Laura Kallmeyer|title=Parsing Beyond Context-Free Grammars|year=2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0|pages=5 and 37}} citing http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf for the proof</ref>

P can also be defined as an algorithmic complexity class for problems that are not decision problems<ref name="Wegener2005">{{cite book|last = Wegener| first=Ingo|author-link=Ingo Wegener|title=Complexity Theory|year=2005|publisher=Springer-Verlag|isbn=978-3-540-21045-0|doi= 10.1007/3-540-27477-4|page=35}}</ref> (even though, for example, finding the solution to a [[2-satisfiability]] instance in polynomial time automatically gives a polynomial algorithm for the corresponding decision problem). In that case P is not a subset of NP, but P∩DEC is, where DEC is the class of decision problems.