《计算复杂性：现代方法》——第2章 NP和NP完全性 2.1 类NP

第2章

NP和NP完全性

如果你曾玩过填字游戏，那你一定知道从头开始游戏远比验证其他人给出的答案难得多。同样，自己动手做数学家庭作业远比阅读和理解老师给的答案难得多。区别在于，寻找填字游戏的答案和解数学题是创造性劳动。验证答案相对容易的原因是其他人已经完成了创造性劳动。

2.1　类NP

现在，我们定义复杂性类NP,由此将“可被高效验证的解”这一直觉概念形式化。在第1章，我们曾说一个问题是“可被高效求解的”，如果它可以被图灵机在多项式时间内求解。于是，问题的解是“可被高效验证的”，指的是该问题的解可以在多项式时间内得到验证。由于图灵机每步只能读一个位，因此这意味着给定的解不能太长——至多是输入长度的多项式。



2.1.1　P和NP的关系

2.1.2　非确定型图灵机


时间： 2024-09-18 08:44:32

《计算复杂性：现代方法》——第2章 NP和NP完全性 2.1 类NP的相关文章

裴礼文数学分析中的典型问题与方法第4章一元函数积分学练习

参考解答见: http://www.cnblogs.com/zhangzujin/p/3527416.html     4.1.1  设 $f(x)$ 在 $[0,1]$ 上连续, 且 $f(x)>0$, 求极限 $\vlm{n}\sqrt[n]{f\sex{\f{1}{n}}f\sex{\f{2}{n}}\cdots f\sex{\f{n-1}{n}}f(1)}$.     4.1.2  考虑积分 $\dps{\int_0^1 (1-x)^n\rd x}$, 证明  $$\bex  C_n^0

裴礼文数学分析中的典型问题与方法第3章一元微分学练习

参考解答见: http://www.cnblogs.com/zhangzujin/p/3527416.html   3.1.1 计算下列函数的指定导数: (1) $\dps{f(x)=\sqrt{\f{(1+x)\sqrt{x}}{\e^{x-1}}}+\arcsin\f{1-x}{\sqrt{1+x^2}} }$, 求 $f'(1)$. (中国人民大学)  (2)  $\dps{f(x)=x^{\sin (\sin x^x)}\ (x>0)}$, 求 $\dps{\f{\rd y}{\rd x

裴礼文数学分析中的典型问题与方法第2章一元函数的连续性练习

参考解答见: http://www.cnblogs.com/zhangzujin/p/3527416.html   2.1.1 研究函数 $\dps{f(x)=\vlm{n}\f{x^n-1}{x^n+1}}$ 的连续性.   2.1.2 设 $$\bex f(x)=\seddm{ \f{\ln(1+x)}{x},&x>0\\ 0,&x=0\\ \f{\sqrt{1+x}-\sqrt{1-x}}{x},&-1\leq x<0 }. \eex$$ 试研究 $f(x)$ 在

裴礼文数学分析中的典型问题与方法第5章级数练习

参考解答见: http://www.cnblogs.com/zhangzujin/p/3527416.html     5.1.1  设 $k,i,j$ 都是自然数, 且 $k=i+j$, 试求级数 $\dps{\vsm{n}\frac{1}{(kn-i)(kn+j)}}$ 的和.     5.1.2  设 $\sed{a_n}$ 为等差数列, $a_{n+1}-a_n=d>0\ (n=1,2,\cdots)$, $m$ 为一正整数. 计算  $$\bex  S=\vsm{n}\frac{1}{

c#扩展方法奇思妙用高级篇八：Type类扩展

Type 类提供了大量的属性和方法,但在一些基础性开发工作中,Type类功能还有些欠缺,尤其上在处理泛型类型时,如可空类型和泛型集合类型.下面的类就针对这些地方进行扩展. 1 public static class TypeHelper 2 { 3 public static bool IsNullableType(this Type type) 4 { 5 return (((type != null) && type.IsGenericType) && 6 (type.

《Haskell趣学指南》—— 第2章，第2.4节类型类入门

2.4 类型类入门 类型类(typeclass)是定义行为的接口.如果一个类型是某类型类的实例(instance),那它必实现了该类型类所描述的行为. 说得更具体些,类型类是一组函数的集合,如果将某类型实现为某类型类的实例,那就需要为这一类型提供这些函数的相应实现. 可以拿定义相等性的类型类作为例子.许多类型的值都可以通过==运算符来判断相等性,我们先检查一下它的类型签名: ghci> :t (==) (==) :: (Eq a) => a -> a -> Bool 注意,判断相等

《21天学通Java（第6版）》—— 导读

前言 21天学通Java(第6版) 有些革命出其不意地吸引了全世界的眼球.Twitter.Linux操作系统和电视剧<Cupcake Wars>的异军突起颠覆了传统思维模式. 而Java语言的巨大成功却在人们的意料之中.自从Java语言于17年前面世以来,人们就对它充满殷切的期望.当Java融入到Web浏览器时,公众以无比的热情欢迎这种新语言的到来. Sun公司创始人Bill Joy在介绍这种新语言时,毫不掩饰其孤注一掷的心态:"15年来,我们一直力图开发出一种更佳的编程语言和环境,

php 面向对象详解_封装性

第七章(5)面向对象详解_封装性 封装性:就是将对象内部的属性或方法封装在自己的对象内部,在对象内部可以被使用或访问,但在对象的外部或者其它对象里不能使用封装的成员. 封装使用的关键字:private 封装的含义: 1.把对象的全部属性和全部方法结合在一起,形成一个不可分割的独立的单位(对象). 2.信息隐蔽,即尽可能的隐蔽内部细节,对外形成一个边界(或者说对外形成一个屏障),只保留有限的对外的接口,使它与外部发生关系.      第七章(6)面向对象详解_封装时所用的四个常用的方法 带"__&

《计算复杂性：现代方法》——2.7　深入理解P、NP及其他复杂性类

2.7 深入理解P.NP及其他复杂性类 2.7.1 NP的哲学意义 2.7.2 NP与数学证明 2.7.3 如果P=NP会怎样 如果P=NP--具体地讲,如果像3SAT这样的一个NP完全问题存在二次时间的高效算法--则世界很可能会变成一个计算乌托邦.数学家将会被高效的证明发现程序取代(该事实在哥德尔1956年的信中就曾被指出,并且20年后又重新被指出).一般而言,对于答案能够被高效地验证(或正确性具有短证明)的任何搜索问题,我们将能够在多项式时间内高效地找到答案或短证明.人工智能(AI)软件将