更改

考虑具有包括线性顺序关系的固定签名的有限结构的所有语言。然后，所有这些语言在 p 中都可以用一阶逻辑表示，只要加上一个合适的最小不动点组合子。实际上，结合顺序，可以定义递归函数。只要签名除了特殊的顺序关系之外，还包含至少一个谓词或函数，因此用于存储这种有限结构的空间量实际上是多项式的，这正是 p 的特征。

考虑具有包括线性顺序关系的固定签名的有限结构的所有语言。然后，所有这些语言在 p 中都可以用一阶逻辑表示，只要加上一个合适的最小不动点组合子。实际上，结合顺序，可以定义递归函数。只要签名除了特殊的顺序关系之外，还包含至少一个谓词或函数，因此用于存储这种有限结构的空间量实际上是多项式的，这正是 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 = NP if and only if P = PH (as the former would establish that NP = co-NP, which in turn implies that NP = PH).

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 name=":38">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 = NP if and only if P = PH (as the former would establish that NP = co-NP, which in turn implies that NP = PH).

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, 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?".Elvira Mayordomo. "P versus NP"  Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004). The word "existential" can even be dropped from the previous characterization, since P = NP if and only if P = PH (as the former would establish that NP = co-NP, which in turn implies that NP = PH).

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, 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?".Elvira Mayordomo. "P versus NP"  Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004). The word "existential" can even be dropped from the previous characterization, since P = NP if and only if P = PH (as the former would establish that NP = co-NP, which in turn implies that NP = PH).

类似地，NP 是一组可以用存在二阶逻辑表达的语言---- 也就是说，二阶逻辑限制排除关系、函数和子集上的全称量化。PH 的语言，PH，对应于所有的二阶逻辑。因此，问题“ p 是 NP 的一个适当子集”可以重新表述为“存在二阶逻辑能够描述语言(有限的线性有序结构与非平凡签名) ，一阶逻辑与最少不动点不能？“ Elvira Mayordomo。"P versus NP"  Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).存在主义这个词甚至可以从前面的角色塑造中去掉，因为 p = NP 当且仅当 p = PH (正如前者建立 NP = co-NP，这反过来意味着 NP = PH)。

类似地，NP 是一组可以用存在二阶逻辑表达的语言---- 也就是说，二阶逻辑限制排除关系、函数和子集上的全称量化。PH 的语言，PH，对应于所有的二阶逻辑。因此，问题“ p 是 NP 的一个适当子集”可以重新表述为“存在二阶逻辑能够描述语言(有限的线性有序结构与非平凡签名) ，一阶逻辑与最少不动点不能？“ Elvira Mayordomo。"P versus NP"  Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).存在主义这个词甚至可以从前面的角色塑造中去掉，因为 p = NP 当且仅当 p = PH (正如前者建立 NP = co-NP，这反过来意味着 NP = PH)。

==逻辑特征==

==逻辑特征【过多逻辑学的专业词汇，我许多句子看不懂，编辑需要重点关注】==

P = NP问题可以用可表达的特定类别的逻辑语句来重新表述，这是描述复杂性这项工作的结果。

P = NP问题可以用可表达的特定类别的逻辑语句来重新表述，这是描述复杂性这项工作的结果。

类似地，NP是一组可在存在二阶逻辑中表达的语言，也就是二阶逻辑，被限制为排除关系、函数和子集上的通用量化。多项式层次结构中的语言PH对应于所有二阶逻辑。因此，问题“P是NP的适当子集”可以重新表述为“存在二阶逻辑能够描述（具有非平凡特征的有限线性有序结构的）语言，而具有最小不动点的一阶逻辑不能吗？”。甚至可以从前面的描述中删除“存在”一词，因为P=NP当且仅当P=PH（因为前者将确定NP=co-NP，这反过来意味着NP=PH）。

类似地，NP是一组存在性二阶逻辑中可表达的语言，也就是强迫排除关系、函数和子集上的通用量化符的二阶逻辑。多项式层次结构中的语言PH对应于所有二阶逻辑。因此，“P是NP的一个恰当子集吗”这个问题可以重述为“是否存在这样一种二阶逻辑，它能够描述（具有非平凡签名但有限线性有序结构的）语言，但具有最小定点的一阶逻辑不能？”。<ref name=":38" />“存在”一词甚至可以从前面的描述中删除，因为P = NP当且仅当P = PH（因为前者将确定NP = co-NP，这进一步说明NP = PH）。

==Polynomial-time algorithms==

==Polynomial-time algorithms==