《计算复杂性：现代方法》——2.2　归约和NP完全性

第2章 NP和NP完全性 如果你曾玩过填字游戏,那你一定知道从头开始游戏远比验证其他人给出的答案难得多.同样,自己动手做数学家庭作业远比阅读和理解老师给的答案难得多.区别在于,寻找填字游戏的答案和解数学题是创造性劳动.验证答案相对容易的原因是其他人已经完成了创造性劳动. 2.1 类NP 现在,我们定义复杂性类NP,由此将"可被高效验证的解"这一直觉概念形式化.在第1章,我们曾说一个问题是"可被高效求解的",如果它可以被图灵机在多项式时间内求解.于是,问题的解是&qu

前 言 计算复杂性理论在过去三十多年中发展迅速.自1990年以来取得的出人意料的结果和基础性的结果本身就可以写出一部书.这些结果涉及的领域非常广泛,包括:经典复杂性类的概率型新定义(IP=PSPACE和各种PCP定理)以及它们在近似算法中的应用,肖尔(Shor)为量子计算机设计的整数因数分解算法,对人们目前处理著名的P?=NP问题 译文用"P?=NP"来表示原文中的"P versus NP".--译者注的各种方法为什么未能获得成功的理解,去随机化理论和基于计算难

2.4 归约网络 回顾一下第0章中的如何安排晚宴以确保任意一对宾客之间均能和睦相处的问题,例0.1将该问题形式化为如下的语言: 归约的赞誉 虽然多项式时间归约概念(以及它的第一个孪生概念--随机多项式时间归约,将在7.6节给出定义)的提出源于NP完全性理论,然而由此引出的对复杂性理论的理解远远超出了NP完全性本身.如今,复杂性理论和密码学(因而本书的许多章节)的相当一部分工作是利用归约为不同的复杂性理论猜想建立联系.为什么复杂性理论学家均擅长于使用归约,而不擅长于踏踏实实地证明图灵机的下界呢?或

前言 虽然大型数据集可能得到更佳的挖掘结果,但未必能获得比小型数据集更好的挖掘结果 对于多维数据,一个主要的问题是在所有维度中搜寻所有挖掘方案之前,是否可以确定某方法在已归约数据集的挖掘和发现中国发挥得淋漓尽致. 一.大型数据集的维度 数据的描述以及特征的挑选,归约或转换可能是决定挖掘方案质量的最终更要问题. 预处理集的3个主要维度通常表示为平面文件即列,行和特征的值因此数据归约的3个基本操作就是删除列,删除行和减少列中值的数量.这些操作的目的是试图删掉不必要的数据来保留原始数据的特征 在准备数

多核CPU中,要很好地发挥出多个CPU的性能的话,必须保证分配到各个CPU上的任务有一个很好的负载平衡.否则一些CPU在运行,另外一些CPU处于空闲,无法发挥出多核CPU的优势来. 要实现一个好的负载平衡通常有两种方案,一种是静态负载平衡,另外一种是动态负载平衡. 1.静态负载平衡 静态负载平衡中,需要人工将程序分割成多个可并行执行的部分,并且要保证分割成的各个部分能够均衡地分布到各个CPU上运行,也就是说工作量要在多个任务间进行均匀的分配,使得达到高的加速系数. 静态负载平衡问题从数学上来说是

我们都知道对于软件而言,最为经典的定义就是程序=算法+数据结构,算法对于软件的重要性不言而喻,甚至可以说算法是程序的灵魂所在.甚至有人说如果计算机系只开设三门课的话,那么一定是:离散数学.编译原理还有算法和数据结构.算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制.其实对于IT人而言,无时无刻都沉浸在算法之中,小到可能只是对于一个简单的一维数组进行排序,大到使用进行实时个性化推荐或者使用机器学习算法预测未来的发展趋

自西方文艺复兴以来,中国在自然科学方面落后西方很多,软件领域也不例外.当然现在中国的许多程序员们对此可能有许多不同的意见,有些人认为中国的程序员水平远落后于西方,有些则认为中国的程序员个人能力并不比西方的程序员差,只是整个软件产业落后而已.     那么,到底中国的程序员水平比西方程序员水平差,还是中国有许多优秀的程序员达到或超过了西方程序员同等水平呢?要解决这个问题,必须先知道程序员有多少种技术层级,每个层级需要什么样的技术水平,然后再比较中国和西方在各个技术层级的人数,就可以知道到底有没有差

译注:map(映射)和reduce(归约,化简)是数学上两个很基础的概念,它们很早就出现在各类的函数编程语言里了,直到2003年Google将其发扬光大,运用到分布式系统中进行并行计算后,这个组合的名字才开始在计算机界大放异彩(那些函数式粉可能并不这么认为).本文我们会看到Java 8在摇身一变支持函数式编程后,map和reduce组合的首次亮相(这里只是初步介绍,后续还会有针对它们的专题). 对集合进行归约 现在为止我们已经介绍了几个操作集合的新技巧了:查找匹配元素,查找单个元素,集合转化.这

更多深度文章,请关注云计算频道:https://yq.aliyun.com/cloud 我的"深度学习论文实现"系列的前三个博客将涵盖2016年由Google Deepmind的Max Jaderberg, Karen Simonyan, Andrew Zisserman and Koray Kavukcuoglu提出的空间变换网络概念.空间变换网络是一个可学习模型,旨在提升卷积神经网络在计算和参数方面的空间恒定性. 在第一部分中,我们将介绍两个非常重要的概念,在理解空间变化层次的内在