NP问题

概念含义

P问题: 多项式复杂度求问题的解, 本质是信息精简 NP问题: 无法用多项式复杂度求问题的解, 对于一个给定的解可以在多项式时间内验证, 本质也是信息精简 NPC问题: 任何NP问题都可以通过多项式复杂度转化为NPC问题 求解: 熵减, 在没有其他信息情况下是不可能的 SAT(The Satisfiability Problem)问题: n个变量的逻辑表达式, 判断是否存在真值

思考

我个人一直是对NP问题有抵触心理的, 具体体现在喜欢物理推演, 而厌恶化学对一个

我好像明白为什么微积分为什么这么恶心了.

今天明白了NP问题和P问题

微积分很多题都是NP问题, 必须先有解,然后去验证 教授指导学生写论文也是NP问题, 大部分情况出错后再改

试图找通法"金钥匙"不是多项式复杂度, 根本就不可能