第(1/3)页

    燕京大学。

    宿舍区。

    “如果任何一个np问题，都能通过一个多项式时间算法，转换为某个np问题，那么这个np问题就称为np完全问题……”

    “说到底，np完全问题也就是多项式复杂程度的非确定性问题……”

    “np=p？”

    “关键就在这个问号上面……”

    陈舟正埋首于书桌前，皱眉整理着自己的思路。

    书桌上，他从斯德哥尔摩带回来的草稿纸，原本还存在一些空白的地方。

    但此刻，已经全部被数学公式，或是记录的文字，给填得满满当当。

    “唉……”轻声叹了口气，陈舟微微沉吟，“还是那个路径，不管是不是明确，它会变化？还是不变化？”

    “如果不变化，是不是可以最终落到确定性上面，就像那些加减乘除之类的计算问题，有着明确的公式，一步一步的计算都是确定性的……”

    “但是，有些问题能按部就班直接计算出来吗？”

    想到这的陈舟，伸手拿出一张崭新的a4草稿纸，写下来两个问题。

    【找大质数的问题】

    【大的合数分解质因数的问题】

    毫无疑问，这是两个最简单的例子。

    也是两个无法按部就班，一步一步直接计算出来的问题。

    没有一个公式，可以一步步推算出来下一个质数应该是多少。

    也不存在一个公式，能够把合数代进去，就直接算出它的分解质因数各自是多少。

    习惯性的用笔点着这两个问题，陈舟此刻打算从最简单的问题入手，去验证自己的思路。

    “这两个都是最简单的非确定性问题，虽然没有确定性的计算公式，但是存在一个算法，可以验证结果的正确与错误……”

    “把这两个问题的思路再延伸的话……”

    “这个算法，假如可以在多项式时间内算出来，那就变成了多项式非确定性问题……”

    “再假如这个问题的所有可能答案，都是可以在多项式时间内，通过这个算法进行正确与否的验算，那就变成了完全多项式非确定性问题……”

    顺着这个思路，陈舟开始梳理了起来。

    即使他在颁奖晚宴上，像发癔症般的抓住了那丝灵感。
    第(1/3)页