OpenAI引起的P/NP科普

简单科普一下，人类问题可大至分为以下层次：

 

1. 真可解，实际可用，P类；

2. 理论可解且有算法，但是只有暴力解，暴力指的是指数暴力，小型问题实际可用，大型问题形同无解。NP类。由于这类问题易构难解，就是构造容易解锁难，它是密码学和加密货币的理论基础。

3. 理论可解，但只有超级暴力解，比指数暴力还低效；例子：围棋比赛

4. 理论可解，但算法未知；例子太小众，略。

5. 理论不可解。对行外太高深，略。

 

P指的是多项式，就是变量是底数。NP一般认为就是指数时间类，变量在幂的指数部分。还有一类算法是介于P和NP之间的叫压指数算法，虽不是完全实际可用，但它把对大型问题的可实际应用尺度大大扩展了。

“小型”，“大型”，指的是指数变量的大小。

OpenAI宣称找到了压指数算法。

 

还有一点要科普的是，对NP类问题，最难的部分叫NPC，恐怖的是对该类问题，只要有一个问题有答案了，所有问题便立刻都答案。

[菲沙河星光]

Typo: 不是“压”， 是“亚”，英语前缀“sub-”。亚指数，sub-exponential .