Editing P (complexity) (section)

==Notable problems in P==
P is known to contain many natural problems, including the decision versions of [[linear programming]], and finding a [[maximum matching]]. In 2002, it was shown that the problem of determining if a number is [[prime number|prime]] is in P.<ref>Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "[http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf PRIMES is in P]", ''Annals of Mathematics'' 160 (2004), no. 2, pp. 781–793.</ref> The related class of [[function problem]]s is [[FP (complexity)|FP]].

Several natural problems are complete for P, including [[st-connectivity|''st''-connectivity]] (or [[reachability]]) on alternating graphs.<ref name="Immerman Reachability">{{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}}</ref> The article on [[P-complete|P-complete problems]] lists further relevant problems in P.