P/NP/NP_complete/NP_hard问题
机器学习面临的问题通常是NP-hard甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获最优解，这就意味着我们构造性地证明了“P=NP”，因此，只要相信“P≠NP”，过拟合就不可避免。
###定义问题
P问题、NP问题、NPC问题和NP hard问题，其中P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系：P=NP?
NP类问题，就是不知道这个问题是不是存在多项式时间内的算法，所以叫non-deterministic非确定性，但是我们可以在多项式时间内验证并得出这个问题的一个正确解（TSP问题）
P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内得到验证
NP-complete问题是如果所有NP问题可在多项式时间内归约成某个NP问题，则该NP问题称为NP完全问题。
同时满足两个条件：（1）该问题是一个NP问题；（2）所有NP问题可以归约为该问题。所以NPC问题既是NP问题的子集，又是NP hard问题的子集，因此NPC问题是NP问题和NP hard问题的交集。
可满足性问题、哈密顿圈问题、巡回售货员问题、最长路径问题都是NPC问题。 装箱(bin packing)问题、背包(knapsack)问题、图的着色(graph coloring)问题以及团(clique)的问题都是著名的NPC问题。
NP_Hard指问题S，满足任何NP问题都可以在多项式级时间复杂度内被归约为S（归约：即被归约的NP问题与S的答案相同，当解决了S时，就同时解决了所有的NP问题）。可以理解为，这是一个比所有NP问题都难的问题。
（NP hard问题不一定是NP问题，有可能是不可判定问题。这时候说明原问题也是不可判定的）
###相互关系
NP hard问题和NPC问题都要求能够在多项式时间内规约成另外一个问题。这里规约的意思是将一个特殊问题一般化，即将原问题推广为一个最一般的、最有概括性、也更难的、计算复杂度更高的问题，这个问题具有最高的计算复杂度，如果这个最一般的问题也能有多项式时间求解算法，那么那些特殊的原问题也能有多项式时间求解算法。
- 假设 N P = P 猜想不成立，那么计算复杂度的相对关系为（按照由低到高）：P < N P < N P C < NPhard
- 假设 N P = P 猜想成立，那么说明所有存在多项式时间验证算法的问题都存在多项式时间求解算法，而NPC本身属于NP问题，因此NPC也存在多项式时间求解算法，所以NPC = P，所以 P = N P = NPC ，属于NP hard问题的一个子集。
正是NPC问题的存在，使人们相信P≠NP
NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决
###其他理解
- 计算机处理的输入常常不是几十个或几千个，而是几百万个的时候，时间复杂度为O ( n 2 ) O(n^2)O(n2)和O ( e n ) O(e^n)O(e**n)的算法，所需的运行次数简直是天壤之别，O ( e n ) O(e^n)O(e**n)指数级的可能运行好几天都没法完成任务，所以才要研究一个问题是否存在多项式时间算法。
- 而我们也只在乎一个问题是否存在多项式算法，因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的
- 最开始的时候，大家不知道NP的定义是存在所谓 最难的 这么一个东西的，各类问题没有固定的比较标准。直到一个叫Cook的数学家做了点CS的工作，他证明了任何一个NP形式的问题都可以转换成 3SAT （某个NP问题）。3SAT 就是说有n个variable，m个clause，每个clause都是某三个variable 或（|） 在一起， 最后再把所有的clause 和（&） 在一起， 问题是：“有没有一种对于这n个variable的取值可以让整个boolean formula的值为true？” 3SAT 这个问题的优点在于它非常的直观清晰。最开始这篇文章没得到什么重视，直到一个非常出名的计算机科学家Levin看到了这篇文章，突然意识到如果这么多问题都等价于 3SAT 问题，那这就很好地揭示了为什么之前那么多算法问题都找不到快速的（多项式级）算法，因为都和3SAT一样难嘛；另外可以用 3SAT 作为对各种计算问题的分界线，那以后只要发现是NP-complete的问题，大家就不用对于每个问题找解法了。由此衍生了很多对于complexity class的研究，而cook-levin这种把NP问题化为3SAT的思想一次又一次起到了至关重要的作用。
PS : 时间复杂度
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
