134
个编辑
更改
跳到导航
跳到搜索
小第489行：
第489行： − + 第531行：
第531行： − 由于描述的复杂性，P=NP问题可以用可表达的特定类别的逻辑语句来重新表述。+ − 考虑包括线性次序关系的固定签名的所有有限结构语言。然后，通过添加合适的最小不动点组合符，P中的所有这些语言都可以用一阶逻辑表示。实际上，这与顺序相结合，允许定义递归函数。只要签名除了可分辨顺序关系之外，还包含至少一个谓词或函数，那么存储此类有限结构所占用的空间量实际上是结构中元素数量的多项式，这就准确地刻画了P。+
→关于证明难度的结果
|-
|-
|相对证明
|相对证明
|想象这样一个世界，每个算法都可以对一个名为oracle（一个可以在固定时间内回答一组固定问题的黑匣子，例如一步解决任何给定旅行商问题的黑匣子）的固定子例程进行查询，oracle的运行时间不计入算法的运行时间。大多数证明（尤其是经典证明）都适用于有oracle的世界，无论oracle做什么。这被称为相对证明。1975年，贝克（Baker,）、吉尔（Gill）和索洛维（Solovay）证明，对于某些oracle，P = NP，而对于其他oracle，P ≠ NP。<ref name=":32" />由于相对证明只能证明对所有可能的oracle都一致正确的陈述，这表明相对证明技术无法解决P = NP。
|想象这样一个世界，每个算法都可以对一个名为oracle（一个可以在固定时间内回答一组固定问题的黑匣子，例如一步解决任何给定旅行商问题的黑匣子）的固定子例程进行查询，oracle的运行时间不计入算法的运行时间。大多数证明（尤其是经典证明）都适用于有oracle的世界，无论oracle做什么。这被称为相对证明。1975年，贝克（Baker）、吉尔（Gill）和索洛维（Solovay）证明，对于某些oracle，P = NP，而对于其他oracle，P ≠ NP。<ref name=":32" />由于相对证明只能证明对所有可能的oracle都一致正确的陈述，这表明相对证明技术无法解决P = NP。
|-
|-
|自然证明
|自然证明
==逻辑特征==
==逻辑特征==
P = NP问题可以用可表达的特定类别的逻辑语句来重新表述，这是描述复杂性这项工作的结果。
用固定签名考虑包括线性次序关系的所有语言的有限结构。【signature不知道如何翻译，[[wikipedia:P_versus_NP_problem#Logical_characterizations|该节]]】然后，通过添加合适的最小不动点组合符，P中的所有这些语言都可以用一阶逻辑表示。实际上，这与顺序相结合，允许定义递归函数。只要签名除了可分辨顺序关系之外，还包含至少一个谓词或函数，那么存储此类有限结构所占用的空间量实际上是结构中元素数量的多项式，这就准确地刻画了P。
类似地，NP是一组可在存在二阶逻辑中表达的语言，也就是二阶逻辑，被限制为排除关系、函数和子集上的通用量化。多项式层次结构中的语言PH对应于所有二阶逻辑。因此，问题“P是NP的适当子集”可以重新表述为“存在二阶逻辑能够描述（具有非平凡特征的有限线性有序结构的）语言，而具有最小不动点的一阶逻辑不能吗？”。甚至可以从前面的描述中删除“存在”一词，因为P=NP当且仅当P=PH（因为前者将确定NP=co-NP，这反过来意味着NP=PH）。
类似地，NP是一组可在存在二阶逻辑中表达的语言，也就是二阶逻辑，被限制为排除关系、函数和子集上的通用量化。多项式层次结构中的语言PH对应于所有二阶逻辑。因此，问题“P是NP的适当子集”可以重新表述为“存在二阶逻辑能够描述（具有非平凡特征的有限线性有序结构的）语言，而具有最小不动点的一阶逻辑不能吗？”。甚至可以从前面的描述中删除“存在”一词，因为P=NP当且仅当P=PH（因为前者将确定NP=co-NP，这反过来意味着NP=PH）。