对于计算机来说,哪些问题是容易计算的,哪些是几乎不可能的?这些是计算复杂性领域的核心问题。本文是对这些问题的鸟瞰。(后附超大彩蛋)
编译:集智俱乐部翻译组来源:quantamagazine原题:A Short Guide to Hard Problems
编译:集智俱乐部翻译组
复杂类之间的可能只有微妙的差异,也可能有著显著的差异,弄清楚类别之间的差异还挺有挑战性。为此,本文把最基本的七个复杂类别放在一起,希望你看完后不要再混淆BPP和BQP了:)
典型问题:
研究者们关心:
NP
这就是NP问题的特点,很难找到正确的解,但是判断一个解是否正确十分容易;
全称:有界误差量子多项式时间
简述:所有能用经典计算机在指数级时间内解决的问题
简述:可以通过包含随机因素的演算法快速解决的问题
推荐阅读
10月25日,集智俱乐部联合腾讯研究院、中信出版集团、北京师范大学系统科学学院,邀请圣塔菲研究所杰出教授和前任所长、畅销科普书《规模》作者杰弗里·韦斯特(Geoffrey West)教授,作为AI & Society 系列沙龙第十一期的主讲嘉宾,带来一场精彩的主题演讲——《地球未来:生物体、城市、公司的生命、生长和死亡》。扫码即刻观看讲座全程,翔实讲座+现场答疑,助你更好理解《规模》!
讲座+答疑 回放地址:
集智AI学园:
集智俱乐部QQ群|877391004
让苹果砸得更猛烈些吧!