NP问题-1
欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
进这里点赞，助力申请简书【人工智能通识】小岛ヾ(≧∇≦感謝≧∇≦)ノ
什么是P问题、NP问题、NPC问题或NP-hard问题？
判定问题Decision problem
判定问题也称之为决定性问题，即是非问题，就是对于给定输入，要输出Yes或者No。
比如判定一个自然数是不是质数，这就是一个判定问题。
比如给定输入整数A和B，要求判定A是否能被B整除。
无论输入什么，都只有两个输出可能，Yes或No
这个判断方法（上图中的算法Algorithm）就称之为决定程序Decision procedure,在计算机编程中就是一个函数或者方法。
如果一个判定问题存在一个能够有效解决的算法，那么就说这个问题是可被判定的Decidable。否则就称之为不可判定的Undecidable。
递归集合Recursive set
对于一个自然数组成的集合N，给定任意一个输入数字A，如果存在一种算法可以在有限的时间内判定数字A是否属于集合N，那么就说这个集合是个递归集合。
递归集合，可判定集合
举个例子，所有素数的集合就是一个递归集合，这并不是说我们可以把所有素数都完整的列出来，而是说我们可以写一个计算机程序来判定任何一个给定的自然数n是否是素数。
这个程序的算法可以是让n分别除以2,3,4,...(n-1)，检查是否能整除。如果其中有一个能整除话n就不是素数，输出结果No。如果都不能整除的话就输出Yes，是素数。
注意这里，因为n是确定的，那么2到n-1也是有限的个数，所以我们的算法一定能算完。虽然我们的算法性能很差(其实只要检查2到根号n就可以)，但这无所谓，因为我们只是要找到一个可以解决问题的算法，而不是要找最优算法。
递归可枚举集合Recursively enumerable set
对于另外一些集合S（也是自然数组成的），只存在那种可以判断某个数字属于这个集合的算法，但这个算法无法对某个数字做出否定判断（不属于S）的算法。对这样的情况我们称之为半可判定集合Semidecidable set或递归可枚举集合Recursively enumerable set(RE)。
半可判定集合，递归可枚举集合
这相当于说，如果数字x在集合S中，f(x)可以输出Yes，但如果x不在S中，那么f(x)将无法输出结果（永无休止的计算，永远没有结果）。
举个例子，所有相邻素数的差组成的集合R，类似[3-2=1,5-3=2,11-7=4,29-23=6,907-887=20...]，即[1,2,4,20...]，这个集合也是无限的，但我们可以尝试编写一个程序来判断n是否属于这个集合R：
- 逐个检查1,1+1,1+2,1+3,...,1+n每个数字是否素数
- 如果只有1和1+n是素数，其他都不是，那么n肯定属于集合R，停止并返回Yes
- 如果除了1和1+n之外中间还有其他素数，那么就检查2,2+1,2+2,2+3,...2+n每个数字是否是素数，以此类推，反复循环，如果除了2和2+n之外中间还有其他素数就开始检查3,3+1,3+2,3+3,...3+n...
对于这个算法，如果n=4的话很快就可以结束并返回Yes，但如果n=5那这个程序就永远不会结束。——实际上我们知道任意素数一定是奇数，奇数之差一定是偶数，5肯定不属于R。
如果n真的在R里面，我们的程序就一定能输出Yes，但如果n实际上不在R里面，我们的程序就只能不停地运行下去，不会输出任何结果。
<未完待续>
进这里点赞，助力申请简书【人工智能通识】小岛ヾ(≧∇≦感謝≧∇≦)ノ
欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
每个人的智能新时代
如果您发现文章错误，请不吝留言指正；
如果您觉得有用，请点喜欢；
如果您觉得很有用，欢迎转载~
END
