The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a

admin2009-02-15 40

问题 The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　applies　only　to　worst-case　complexity.　Being　NP-complete　does　not(68)that　a　problem　is　intractable　on　the　average　case.　Indeed,　some　NP-complete　problems　are　"(69)on　average",　though　some　may　not　be.　Levin　initiated　the　study　of　average-case　intractability,　He　showed　that　a　bounded　tiling　problem　under　a　simple　distribution　is　average-case　NP-complete.　Since　then,　several　additional　average-case　NP-complete　problems　have　been　shown　within　Levin’s(70).　This　paper　is　intended　to　provide　a　comprehensive　survey　of　average-case　NP-complete　problems　that　have　been　published　so　far,　and　the　techniques　of　obtaining　these　results.

选项 A、framework
B、problem
C、basis
D、foundation

答案A

解析

转载请注明原文地址:https://kaotiyun.com/show/1HxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a

软件设计师上午基础知识考试

软考中级

在系统转换的过程中，旧系统和新系统并行工作一段时间，再由新系统代替旧系统的策略称为(19)；在新系统全部正式运行前，一部分一部分地代替旧系统的策略称为(20)。

在路由表中设置一条默认路由，目标地址应为(46)，子网掩码应为(47)。

在距离矢量路由协议中，可以使用多种方法防止路由循环，以下选项中，不属于这些方法的是(37)。

ARP协议的作用是(20)，ARP报文封装在(21)中传送。

某Apache服务器的配置文件httpd.conf包含如下所示配置项。在(32)处选择合适的选项，使得用户可通过http：//www.test.cn访问到该Apache服务器；当用户访问http://111.25.4.30:80时，会访问到(33)虚拟主

下面的地址中，属于本地环路地址的是(53)。

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和2位终止位，若每秒钟传送100个字符，采用4相相位调制，则码元速率为(16)，有效数据速率为(17)。

在面向对象分析过程中，用概念模型来详细描述系统的问题域，用(5)来表示概念模型。(6)关系用于表示类与类、接口与接口之间的继承关系；在Java中，用(7)关键字来直接表示这种关系。

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

软件设计中划分模块的一个准则是(10)。两个模块之间的耦合方式中，(11)的耦合度最高；一个模块内部的内聚种类中，(12)内聚的内聚度最高。(12)

横沙岛是中国第三大岛，是上海主要的柑橘生产基地。()

肝硬化患者，出现肾功能衰竭，最可能的原因是()

茯苓与薏苡仁除能利水渗湿外，还可

A、太阳B、阳明C、少阳D、太阴E、厥阴头顶痛属

下列哪些选项正确体现了我国民事诉讼法的处分原则?()

以下对函证内容的表述中，恰当的有()。

设f(x)在[1，2]上连续，在(1，2)内可导，证明：存在ξ∈(1，2)，使得ξf’(ξ)-f(ξ)=f(2)-2f(1)．

CA机构的()使得攻击者不能伪造和篡改证书。

有以下程序#includevoidfun(inta,intb,intc){a=b;b=c;c=a;}main(){inta=10,b=20,c=30;fun(a,b,c);printf("%d,%d,%d\n",c,b,a);}程序运行后

WhatissaidaboutHarry’sbrother?

The notion of NP-completeness has provided a(66)mathematical definition for(67)intractability of NP problems. But this measure a

软件设计师上午基础知识考试

软考中级

在系统转换的过程中，旧系统和新系统并行工作一段时间，再由新系统代替旧系统的策略称为(19)；在新系统全部正式运行前，一部分一部分地代替旧系统的策略称为(20)。

在路由表中设置一条默认路由，目标地址应为(46)，子网掩码应为(47)。

在距离矢量路由协议中，可以使用多种方法防止路由循环，以下选项中，不属于这些方法的是(37)。

ARP协议的作用是(20)，ARP报文封装在(21)中传送。

某Apache服务器的配置文件httpd.conf包含如下所示配置项。在(32)处选择合适的选项，使得用户可通过http：//www.test.cn访问到该Apache服务器；当用户访问http://111.25.4.30:80时，会访问到(33)虚拟主

下面的地址中，属于本地环路地址的是(53)。

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和2位终止位，若每秒钟传送100个字符，采用4相相位调制，则码元速率为(16)，有效数据速率为(17)。

在面向对象分析过程中，用概念模型来详细描述系统的问题域，用(5)来表示概念模型。(6)关系用于表示类与类、接口与接口之间的继承关系；在Java中，用(7)关键字来直接表示这种关系。

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

软件设计中划分模块的一个准则是(10)。两个模块之间的耦合方式中，(11)的耦合度最高；一个模块内部的内聚种类中，(12)内聚的内聚度最高。(12)

横沙岛是中国第三大岛，是上海主要的柑橘生产基地。()

肝硬化患者，出现肾功能衰竭，最可能的原因是()

茯苓与薏苡仁除能利水渗湿外，还可

A、太阳B、阳明C、少阳D、太阴E、厥阴头顶痛属

下列哪些选项正确体现了我国民事诉讼法的处分原则?()

以下对函证内容的表述中，恰当的有()。

设f(x)在[1，2]上连续，在(1，2)内可导，证明：存在ξ∈(1，2)，使得ξf’(ξ)-f(ξ)=f(2)-2f(1)．

CA机构的()使得攻击者不能伪造和篡改证书。

有以下程序#includevoidfun(inta,intb,intc){a=b;b=c;c=a;}main(){inta=10,b=20,c=30;fun(a,b,c);printf("%d,%d,%d\n",c,b,a);}程序运行后

WhatissaidaboutHarry’sbrother?

The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a