P、NP、NP-hard问题
定义
- P Problem: 任意性,对于任意的输入规模n,问题都可以在n的多项式时间内得到解决;
- NP(Non-deterministic Polynomial) Problem: 存在性,可以在多项式的时间里验证一个解的问题;
- NPC(Non-deterministic Polynomial Complete) Problem: 满足两个条件 (1)是一个NP问题 (2)所有的NP问题都可以约化到它。可以理解为NP的泛化问题。
- NP-Hard Problem: 满足NPC问题的第二条,但不一定要满足第一条 —> 不一定可以在多项式时间内解决的问题
搞笑版P=NP证明
反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证,我们认定这样的科学家的存在性为真。但是,因为P = NP,该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生(虽然这样的科学家试图发现这样的一个证明),我们得到了矛盾。