复杂性理论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)

(0)

相关推荐

  • To P or not to P——这是最伟大的计算机数学问题

    2000年5月24日,新罕布什尔州的克莱数学研究所列出了数学和计算机科学中七个未解决的问题.解决其中任何一个问题的奖励是该研究所提供的一张100万美元的支票.然而,直到今天,这些问题中只有一个被解决了 ...

  • 2000年图灵奖

    大家好,我是执念斩长河.今天讲述的是中国首位图灵奖获得者姚期智.图灵奖奖励他为计算机复杂性理论做出巨大的贡献.读完本篇博文大家轻松获得: 姚期智论文涵盖计算机全部复杂性 破解最小生成树线性复杂度的顶级 ...

  • 算法的复杂性理论

    我们如何衡量算法的速度 复杂度理论是对算法运行所需时间量(取决于输入大小)的研究. 这对于软件开发人员理解非常有用,因此他们可以高效地编写代码. 有两种类型的复杂性: 空间复杂度:一个算法需要运行多少 ...

  • 三角洲理论 转折点的分类

    三角洲理论  转折点的分类 一个DELTA高点必须是两个DELTA低点之间所有最高价中的最高价. 一个DELTA低点必须是两个DELTA高点之间所有最低价中的最低价. 在90%的情况下,只需要这一条就 ...

  • 关于复杂性理论的若干随想

    第一推动丛书综合系列:复杂 作者:[美] 梅拉妮?米歇尔 1.秩序如何从混沌中涌现? "世界历史中,秩序如何从chaos中涌现?"我的理解是只能对历史进行事后描述,而无法进行事前预 ...

  • 中医理论—方剂的分类

    方剂是怎么分类的?相信这是大家非常想了解的问题.下面医学教育网小编为大家搜集整理了相关信息,希望对大家能有所帮助. 按证候分类 <伤寒论>内将方剂按太阳.阳明.少阳.太阴.少阴.厥阴六经证 ...

  • 丽水景点101个分类整理

    备注:为搜集更多一直在努力,有错漏的请跟帖补正,请文明留言!祝您旅途愉快,平安是福! 景点过多,只写景点名称和图片,至于详细介绍就大家自己搜索资料了 丽水著名旅游景点: 东西岩 云中大漈 云和梯田景区 ...

  • 课程改革中英语教师教学观念转变及其促进——基于复杂性理论

    作者简介 杜小双/北京外国语大学英语学院博士研究生 新时代以来,我国基础英语教育进入新的发展阶段,致力于培养具有中国情怀.国际视野和跨文化沟通能力的时代新人.新一轮基于核心素养的英语课程改革更加凸显学 ...

  • 波浪理论:2、调整浪的形态及分类(实例讲解)

    调整浪较为复杂,变体很多,是比较容易出错的地方.但万变不离其宗,最终可分为四大类:锯齿形.平台型.三角形和联合型. 一.锯齿形(结构5-3-5) 1.锯齿形调整浪最常出现于大周期2浪中,其次是B浪和X ...

  • 波浪理论:1、推动浪的识别及分类(实例讲解)

    从今天开始,我打算做个合集专门分享下我对波浪理论在实盘中的理解及操作策略.另外关于缠绕理论在股市中的实例操作我也会做个合集. 首先,这篇文章再重复讲解下波浪里的推动浪. 推动浪按形态可分为2大类:标准 ...

  • 经典名篇‖陈椽:茶六大类分类的理论与实际

    我国是茶树原产地,最早发现茶的鲜叶有治病的功效,距今已有四.五千年了.我国利用茶叶也最早,据历史资料,商朝(约公元前16 - 11世纪)鲜叶晒干作贡品,西周(约公元前11世纪 - 公元前771年)茶作 ...