大多数决策问题是不能用程序解决的
决策问题：对于输入的问题，它的回答要么是YES要么是NO
- 计算机程序：计算机程序的集合是可数的。集合形如
想想程序都是"人"一个一个写下来的，他们存在硬盘上实际也是一系列的0 1 组合，也就是说它是一个可数的数。这里需要去掉错误的程序，错误的程序本身是无法解决问题的。
表示空串
- 决策问题：决策函数的集合是不可数的。
每一个决策问题可以看做是一个输入是有限的字符串，输出是0 1的函数。所有的这些函数组成的集合假设他是可数的
所有集合的元素为
,
,
...
,这样的构造是可以无限进行下去。定义一个新的无限长的字串：
,其中
其中
表示原集合中的一个结果，
表示
肯定和
不可数的集合原数肯定是比可数的集合要大，这就意味着大多数的决策问题是无法用程序解决的。
证明出处，见第3小节
不可用程序解决的一个问题示例
比如最后一个进来的人把门关上，实际上每个进来的人都不知道自己是不是最后一个人，因为将来任何时候都有可能有人进来，这种情况，实际上就无法用程序的方式写下来。如果你知道一共有多少个人，那么是明白自己是否是最后一个进来的人，但关键是你不知道一共有多少个人，所以你只能让这个程序一直跑下去，但是跑不出结果
科普P和NP
- P: 多项式时间内能够解决的问题
- EXP: 指数时间内能够解决的问题
- R: 能够在有限时间内解决的问题，R指recursive
halt problem,运行一段代码，它会停止吗？它在有限的时间内能够解决，只要一直运行这个程序就知道
- NP: nondeterministic polynomial。它的答案能在多项式时间内验证。它通过某种“运气成分”的算法来在多项式时间内解决决策问题。
验证是指如果决策问题的答案是YES，能够证明它是正确的,并且证明的验证所花的时间在多项式时间之内。
所谓的运气就是说只需要一次尝试就找到了解决问题的方法。
nondeterministic model指算法本身来猜测，最终得到一个YES或者NO的回答，得到的猜测本身如果问题本身是YES，那么它的回答一定是YES
NP先关的一些概念
P!=NP: 证明问题要比验证问题要难
去证明一个问题需要很多的“灵光”一现，而验证问题只要描述的够精确，按照特定的步骤去执行，保证上下连贯，基本是没有问题。这里的“灵光”也就是说的“运气”
对于P的问题可以在任何计算机上面做实现，但是NP需要机器能够神奇的知道那种方法能够获得正确的解答。而这种机器能够神奇的知道正确答案的是不存在的。也就是说不存在"工程上的幸运"
从集合上来说就是存在这样的问题，它属于NP，但是不属于P
NP-hard: 起码和在NP里头的问题一样的难
NP-complete:
比如 俄罗斯方块问题
NP-complete问题之间都可以互相转化（reduce）
问题转换(Reduction)
转换一个问题A到一个问题B，这样表示B起码和A一样难
比如把没有权重的最短路径问题，转换成有权重的最短路径问题
