数学
P等于NP吗?
遥远的地平线为什么重要
它问的是:每个答案容易验证的问题,是否也容易求解?如果是,交通运输就能得到最优调度,使人员和货物的运送更快、更便宜,但公钥密码学将变得不可能。
我们已知
1971年提出:如果一个问题容易验证,它是否也容易求解?
阻碍所在
好几大类证明技术已被证明不够用。
当前线索
几何复杂性理论,电路下界。
子问题
- 能否证明某个明确给出的问题需要规模超过线性的布尔电路?目前已知最好的下界仅约为4n。
- NP是否不同于co-NP?等价地说,是否不存在一个能为所有重言式给出短证明的证明系统?
- 哪些证明技术能够突破已知的“相对化”和“自然证明”障碍?
相关问题
来源
尚未经专家审阅。
最近核实: 2026-11-18
本问题的修改记录
返回地图 →