You need to enable JavaScript to run this app.
最新活动
大模型
产品
解决方案
定价
生态与合作
支持与服务
开发者
了解我们

为何三等分角等古典几何问题无法作为P≠NP的证明依据?

为何三等分角等古典几何问题无法作为P≠NP的证明依据?

这个问题问得特别戳中要害!不少刚入门计算复杂度的朋友都会有这个联想——毕竟三等分角看起来完美符合“验证超简单、求解做不到”的特征,但它和P≠NP的证明之间,其实隔着好几个核心的概念鸿沟。

  • 计算模型完全不匹配
    P和NP问题的定义,是牢牢绑定在图灵机这个计算模型上的。简单来说,所有讨论的“算法”都是图灵机能执行的操作:用二进制编码数据、按指令一步步计算,处理的是离散的、可数字化的问题。而古典尺规作图是一个完全独立的计算模型,它的“合法操作”只有画直线、画圆,处理的是连续的几何对象,和图灵机的规则压根不是一回事。P/NP讨论的是“图灵机能不能在多项式时间内解决/验证”,而三等分角的“不可能”,是尺规作图规则下的结论,和图灵机的能力没有任何关系。

  • 问题的核心范畴不一样
    P和NP问题都是判定问题——输入一个实例,输出“是”或“否”的二选一问题,而且前提是“这个问题存在解的情况下,图灵机能不能找到或验证”。但三等分角本质是个构造性问题:要求你实际画出符合条件的几何图形。更关键的是,它不是“图灵机没法在多项式时间内解决”,而是在尺规作图的规则下,无论给你多少时间,都不存在能解决所有实例的方法——哪怕无限时间也不行。而P/NP的讨论前提是“问题是可解的”,只是关心解的时间复杂度,连“可解”这个前提都不满足,自然没法套到P/NP的框架里。

  • “验证”的定义也不在一个维度
    你觉得三等分角的验证很简单,但P/NP里的“验证”,特指图灵机在多项式时间内,验证一个给定的“解”是不是对应输入的正确答案。你验证一个角是不是三等分角,是在几何直观里的操作,不是图灵机意义上的验证。而且对图灵机来说,首先得把“角”“三等分线”这些几何对象编码成它能处理的数字(比如实数坐标),但尺规作图能处理的数只是代数数的一小部分(二次扩张的数),而图灵机完全可以用数值方法算出三等分角的近似解,只是没法用尺规画出来而已——这和“图灵机没法解决”完全是两码事。

总结一下:三等分角的“不可能”,是尺规作图这个特定模型下的构造性不可能,而P/NP是图灵机模型下的时间复杂度问题,两者的讨论语境、底层模型、问题类型都完全不兼容,所以根本没法用来证明P≠NP。

备注:内容来源于stack exchange,提问作者Sentry

火山引擎 最新活动