Editing P versus NP problem (section)

==Logical characterizations==
The P&nbsp;=&nbsp;NP problem can be restated as certain classes of logical statements, as a result of work in [[descriptive complexity]].

Consider all languages of finite structures with a fixed [[signature (logic)|signature]] including a [[linear order]] relation. Then, all such languages in P are expressible in [[first-order logic]] with the addition of a suitable least [[fixed-point combinator]]. Recursive functions can be defined with this and the order relation. As long as the signature contains at least one predicate or function in addition to the distinguished order relation, so that the amount of space taken to store such finite structures is actually polynomial in the number of elements in the structure, this precisely characterizes P.

Similarly, NP is the set of languages expressible in existential [[second-order logic]]—that is, second-order logic restricted to exclude [[universal quantification]] over relations, functions, and subsets. The languages in the [[polynomial hierarchy]], [[PH (complexity)|PH]], correspond to all of second-order logic. Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?".<ref>Elvira Mayordomo. [http://www.unizar.es/acz/05Publicaciones/Monografias/MonografiasPublicadas/Monografia26/057Mayordomo.pdf "P versus NP"] {{webarchive|url=https://web.archive.org/web/20120216154228/http://www.unizar.es/acz/05Publicaciones/Monografias/MonografiasPublicadas/Monografia26/057Mayordomo.pdf |date=16 February 2012 }} ''Monografías de la Real Academia de Ciencias de Zaragoza'' 26: 57–68 (2004).</ref> The word "existential" can even be dropped from the previous characterization, since P&nbsp;=&nbsp;NP if and only if P&nbsp;=&nbsp;PH (as the former would establish that NP&nbsp;=&nbsp;co-NP, which in turn implies that NP&nbsp;=&nbsp;PH).