更改

|-

|-

|自然证明

|自然证明

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

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

|-

|-

|代数证明

|代数证明