Editing P (complexity) (section)

==History==
[[Dexter Kozen|Kozen]]<ref>{{cite book | last = Kozen | first = Dexter C. | year = 2006 | title = Theory of Computation | publisher = Springer | isbn = 978-1-84628-297-3 | page = 4}}</ref> states that [[Alan Cobham (mathematician)|Cobham]] and [[Jack Edmonds|Edmonds]] are "generally credited with the invention of the notion of polynomial time," though [[Michael O. Rabin|Rabin]] also invented the notion independently and around the same time (Rabin's paper{{sfn|Rabin|1967}} was in a 1967 proceedings of a 1966 conference, while Cobham's{{sfn|Cobham|1965}} was in a 1965 proceedings of a 1964 conference and Edmonds's{{sfn|Edmonds|1965}} was published in a journal in 1965, though Rabin makes no mention of either and was apparently unaware of them). Cobham invented the class as a robust way of characterizing efficient algorithms, leading to [[Cobham's thesis]].  However, [[Henry Cabourn Pocklington|H. C. Pocklington]], in a 1910 paper,<ref>{{cite journal | last = Pocklington | first = H. C. | author-link=H. C. Pocklington | year = 1910–1912 | title = The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]] | volume = 16 | pages = 1–5}}</ref><ref>{{Cite book | last=Gautschi | first=Walter | author-link=Walter Gautschi | title=Mathematics of computation, 1943–1993: a half-century of computational mathematics: Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia | year=1994 | publisher=American Mathematical Society | location=Providence, RI  | isbn=978-0-8218-0291-5 | pages=503–504}}</ref> analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that ran in (moderately) exponential time.