复杂性理论101：问题分类
如何知道问题的类型和分类
作为数据科学家（或开发人员），我们每天致力于为面临的问题构建和开发新的解决方案。我们创建算法，编写代码，并针对我们遇到的问题的不同实例进行测试。
此过程中的一个重要步骤是定义问题的类型并将其分类。此步骤使我们在继续开发过程之前就知道我们要解决的问题是否可以解决。
复杂性理论是计算机科学的一个子领域，该领域负责将问题分类为一组类别，这些类别指定了这些问题的可解决性。我可以肯定，在您作为数据科学家，程序员或计算机科学专业的学生/爱好者的过程中，您遇到过诸如“这是NP问题”或“此问题可以在P时间内解决”之类的术语，或者“ NP不等于P！”。
但是，这些类别到底是什么意思？以及我们如何理解哪些问题可以解决，哪些不是解决的？如果问题无法解决，那么我们能做些什么来最好地解决该问题呢？
复杂性理论101：Big O简介
为什么每个数据科学家都应该关心算法复杂性？
希望本文将帮助您回答上述问题，并加深您对不同复杂性类别的理解。为了解释不同的分类，让我们坚持一个非常常见的问题，您和您的朋友想出去吃晚饭。现在，您需要决定吃什么。
此问题可以轻松转换为编程术语。假设您正在从事一个项目，并且要求您向其中添加新功能。添加特定功能有多容易？如果您考虑一下，从根本上说，它决定吃什么。
容易的问题（P）
您正与朋友坐在一起，而且都饿了。您建议出去吃披萨，但您的朋友今天不觉得披萨。因此，他们建议去吃寿司，但是你不能处理生鱼。那持续了一段时间，你们俩都变得饥饿了。
最终，您说，“让我们选择最方便的选择。”那是离您最近的地方。您开始根据其与当前位置的距离对顶部选项进行排序。
可以使用诸如Y（到达餐厅的时间）= 10 X（到结果的距离）之类的方程来数学描述此问题。10分钟是您需要步行1公里的分钟数。这种数学上的方程式称为多项式。
这里是分类多项式时间的来源。P问题通常并不有趣，但是我们每天都会遇到一些问题，例如排序和搜索算法。
难题（EXP）
让我们来解决我们的问题。现在，不仅是您和您的朋友；您的父母和兄弟姐妹也将加入您的晚餐。您仍然可以采用与只有两个人并去最近的地方时相同的方法，也可以想到更好的解决方案。
您要求每个人说他们想吃什么，并试图说服其他人选择相同的东西。在P解决方案中，每个人都选择一个位置，然后最接近的一个是获胜者。
但是，现在，每个人都必须做出一个以上的决定，每个人都必须选择一个地点并就另一个人的建议做出决定。
现在，该解决方案变得更加复杂。为了用数学术语描述它，我们可以说Y（决定所需的时间）=X²其中X是我们拥有的人数。现在这变成了指数（EXP）问题，解决该问题所需的时间将比采用P方法的时间长。
可解决的问题（R）
到目前为止，尽管我们决定吃什么要花多长时间，但我们最终还是决定吃了。两种决定方法最终都导致了解决方案。那就是可解决的问题。R问题是可以在有限时间内解决的问题。无论时间是秒，小时还是天，只要是有限的时间，问题都可以解决。
您可能现在想知道，是否存在需要无限时间解决的问题？
答案是肯定的-停顿的问题。问题陈述是：“我们是否可以设计一种通用算法来确定给定程序是否会因给定特定输入而停止？”通用一词使这个问题无法解决，因为除非我们尝试查看程序是否停止，否则我们无法概括该程序何时停止。
这个问题被称为不可确定的，因此在无限时间内无法解决。暂停问题并不是计算机科学中唯一无法解决的问题；您可以在此处找到更多问题。
确定性和非确定性
> Image by the author (made using Canva)
当我们编写代码来解决特定问题时，通常会以确定性方式进行。我们编写了一系列循环，条件语句，以使我们到达想要去的地方。解决问题的另一种方法是以不确定性的方式进行。
以不确定性的方式，我们通过提问和/或猜测来解决问题，直到获得所需的答案。
回到我们的进餐困境，可以说，与其决定每个人与我们之间的相对距离，不让每个人辩论并证明自己的选择，不如将选择记下来并让猫咪决定哪个获胜者。因此，您将纸张放在猫的前面，然后等待其将爪子放在其中一张上。
使用这种方法，您可以确定地解决问题。这种类型的解决方案可以解决P型问题，并且可以采用一种神奇的不确定性方法更快地解决它们。这些类型的问题被分类为NP。
P = NP吗？
寻找一个不确定的解决方案通常是运气。您很幸运，您有一只猫来选择适合自己的饮食，但并非所有人都养猫。
在计算机科学方面，人们在P = NP与否之间存在分歧。有人说我们开发一种不确定的方法来解决所有P问题只是时间问题。其他人则认为某些问题无法非确定性地解决。谁是正确的？没人知道;只有时间会证明这一点。
NP问题
也许我们在计算机科学中最有趣的问题是NP问题。1970年，一位名叫理查德·卡普（Richard Karp）的数学家证明我们可以将所有SAT（可满足性）问题都简化为NP，并列出了21个NP完全问题。
如果您以前曾经历过该问题，则可能已经注意到，尽管这些问题无法解决，但您仍可以在教科书中找到一些解决方案。一个例子是旅行商问题。尽管该问题被定义为NP-hard，但是在某些特殊情况下，一些近似解决方案可以解决该问题。
> Image by the author (made using Canva)
NP硬性与NP完整性
只要是决策问题，任何可以在P时间内不确定地解决的NP问题都称为NP完全问题。NP-hard是下一个级别。NP难题可以在P时间内还原为NP完全问题，而不是诸如停顿问题之类的决策问题。
结论
复杂性理论是计算机科学的重要子领域之一，它根据需要解决的时间对问题进行分类。值得一提的是，复杂性理论并不十分在意用于解决特定问题的算法，而是问题本身。
我们比最初想像的更多地遇到NP难题和NP难题。拥有分类和理解这些问题的类型所需的知识可以帮助我们找到更好的答案，或者将问题简化为P型问题以符合我们的需求。
对复杂性理论和不同的问题分类有更深入的了解肯定会使您的工作受益，并且有一天可能会节省下来。
(本文由闻数起舞翻译自Maarten Grootendorst的文章《Complexity Theory 101: Problems Classification》，转载请注明出处，原文链接：https://towardsdatascience.com/complexity-theory-101-problems-classification-9793f05e42e1)