更改

==关于证明难度的结果==

==关于证明难度的结果==

尽管P=NP问题本身仍然是开放的，有着100万美元的奖金和大量专门的研究，为了解决这个问题的已经产生了几种新技术。尤其是与P=NP问题相关的一些最富有成效的研究表明，现有的证明技术不足以回答这个问题，因此意味着需要新的技术方法。

P = NP问题仍然还未解决，虽然它有着100万美元的奖金并且有大量专门的研究，以及为了解决这个问题已经产生了几种新技术。尤其是与P=NP问题相关的一些最富有成效的研究表明，现有的证明技术不足以解决这个问题，因此意味着需要新的技术方法。

作为表面问题困难的额外证据，计算复杂性理论中的所有已知的证明技术基本上都属于以下分类，它们都无法有力证明P≠ NP:

作为额外表现问题困难的证据，计算复杂性理论中的所有已知的证明技术基本上都属于以下类别，它们都无法有力证明P ≠ NP:

{| class="wikitable"

{| class="wikitable"

|-

|-

!定义

!定义

|-

|-

|相对化证据

|相对证明

|想象一下，在一个世界里，每个算法都可以对一个名为oracle（一个可以在固定时间内回答一组固定问题的黑匣子，例如一步解决任何给定旅行商问题的黑匣子）的固定子例程进行查询，oracle的运行时间不计入算法的运行时间。大多数证明（尤其是经典证明）都适用于有神谕的世界，无论oracle做什么。这些证明被称为相对化。1975年，贝克、吉尔和索洛维证明，对于某些oracle，P=NP，而对于其他oracle，P≠ NP。由于相对化证据只能证明对所有可能的预言都一致正确的陈述，这表明相对化证据无法解决P=NP。

|想象这样一个世界，每个算法都可以对一个名为oracle（一个可以在固定时间内回答一组固定问题的黑匣子，例如一步解决任何给定旅行商问题的黑匣子）的固定子例程进行查询，oracle的运行时间不计入算法的运行时间。大多数证明（尤其是经典证明）都适用于有神谕的世界，无论oracle做什么。这些证明被称为相对化。1975年，贝克、吉尔和索洛维证明，对于某些oracle，P=NP，而对于其他oracle，P ≠ NP。由于相对化证据只能证明对所有可能的预言都一致正确的陈述，这表明相对化证据无法解决P=NP。

|-

|-

|自然证据

|自然证明

|1993年，亚历山大·拉兹博罗夫（Alexander Razborov）和史蒂文·鲁迪奇（Steven Rudich）为电路复杂度下限定义了一类通用的证明技术，称为自然证明。当时，所有已知的电路下界都是自然的，电路复杂性被认为是解决P=NP的一种非常有前途的方法。然而Razborov和Razich证明如果单向函数存在，那么没有一种自然证明法可以区分P和NP。虽然单向函数从未被正式证明存在，但大多数数学家认为它们确实存在，证明它们存在的证据将比P≠ NP更有力。因此，仅自然证明不太可能解决P=NP。

|1993年，亚历山大·拉兹博罗夫（Alexander Razborov）和史蒂文·鲁迪奇（Steven Rudich）为电路复杂度下限定义了一类通用的证明技术，称为自然证明。当时，所有已知的电路下界都是自然的，电路复杂性被认为是解决P=NP的一种非常有前途的方法。然而Razborov和Razich证明如果单向函数存在，那么没有一种自然证明法可以区分P和NP。虽然单向函数从未被正式证明存在，但大多数数学家认为它们确实存在，证明它们存在的证据将比P≠ NP更有力。因此，仅自然证明不太可能解决P=NP。

|-

|-

==声称的解答==

==声称的解答==

虽然P对NP问题通常被认为是未解决的，许多业余和一些专业研究人员已经提出了解决方案。Gerhard J.Woeginger保持着一份列表，截至2016年，该列表包含62个据称是P=NP的证明，50个P的证明≠ NP，2个证明问题是不可判定的，1个证明问题是不可判定的。一些试图解决P对NP的尝试得到了媒体的短暂关注，尽管这些尝试后来遭到了驳斥。

虽然P/NP问题通常被认为是不可解决的，许多业余和一些专业研究人员声称提出了解决方法。格哈德·J·沃金（Gerhard J.Woeginger）维护着一份列表，截至2016年，该表包含62个据称是P = NP的证明，50个P ≠ NP的证明，2个问题不可证明的证明，1个问题不可判定的证明。一些试图解决P/NP的尝试得到了媒体的短暂关注，尽管这些尝试后来遭到了反驳。

==Logical characterizations==

==Logical characterizations==