（转载）P=！NP发现与尝试证明的历史

[forecasting]

此帖转自 forecasting 在 STEM 的帖子：P=！NP发现与尝试证明的历史

见图


但引入电路复杂性，后被人证明不会有自然证明，因此解决不了这个问题。至于PCP层级引入，仅仅证明了NP-Hard问题不可近似，并没有暗示NP！=P。现在只有有限模型论方法还有希望解决这个问题