首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
The notion of NP-completeness has provided a(66)mathematical definition for(67)intractability of NP problems. But this measure a
The notion of NP-completeness has provided a(66)mathematical definition for(67)intractability of NP problems. But this measure a
admin
2009-02-15
28
问题
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、difficult
B、easy
C、hard
D、intractable
答案
B
解析
转载请注明原文地址:https://kaotiyun.com/show/mHxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
驻留在多个网络设备上的程序在短时间内同时产生大量的请求消息冲击某Web服务器,导致该服务器不堪重负,无法正常响应其他合法用户的请求,这属于(39)。
在Windows中运行(29)命令后得到如下图所示的结果,该命令的作用是(30)。
E1载波把32个信道按(11)方式复用在一条2.048Mb/s的高速信道上,每条话音信道的数据速率是(12)。
立即寻址方式中,数据放在(22)。
现代计算机体系结构的发展突破了冯.诺依曼的体系结构,主要表现在(61)。多机系统与多计算机构成的计算机网络差别的主要特征是(62)。面向对象程序设计以(63)为基本的逻辑构件,用(64)来描述具有共同特征的一组对象,以(65)为共享机制,共享类中的方法和数
(41)是在一个公司发给另一个公司的报文上,连同报文和签名一起做一个摘要的方法。目前的产品能够做到的最高安全级别是(42)级。仔细阅读日志属于(43)的内容。在网络安全策略中,属于半主动网络安全策略的方法是(44)。在故障报告中,设备运行出现错误状态用(4
IPv6是下一代IP协议。IPv6的基本报头包含40个字节,此外还可以包含多个扩展报头。基本报头中的(50)字段指明了一个特定的源站向一个特定目标站发送的分组序列,各个路由器要对该分组序列进行特殊的资源分配,以满足应用程序的特殊传输需求。按照IPv6的地址
信元是信元交换的单位。为控制差错,在信元中包括CRC校验和,其生成公式为(6),校验和对(7)进行校验。信元交换采用(8)技术进行复用。在交换过程中,当实施VP交换时,其中VPI、VCI的变化情况是(9)。若在交换过程中出现拥塞,该信息被记录在信元的(10
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
Thepurposeoftherequirementsdefinitionphaseistoproduceaclear,complete,consistent,andtestable(71)ofthetechnicalr
随机试题
下列各项中,哪项更有助于鉴别股骨颈骨折与股骨粗隆间骨折
机体处于寒冷环境中时,维持体热平衡的途径有
免疫抑制剂治疗ITP,正确的是
某慢性肾功能衰竭病人,血钾>6.5mmol/L时,给予10%葡萄糖酸钙静脉注射,其作用机制是
个人的独创的行为模式被其他社会成员所仿效,并广泛地推行,就可以形成一种新的行为模式。这体现了()。
学校中物质文化、制度文化和精神文化的统一体是()。
徘徊:徜徉
已知f(x)在[0,1]上连续,在(0,1)内可导,且f(1)=1,证明:在(0,1)内至少有一点ξ,使得(1+ξ)2f′(ξ)=1.
Hundredsofspeciesofmarinelifemanagetosurviveeveninthedarkestdepthsoftheocean.Thesetenantsofthedeephaveevo
Somedirectorshavethecompanysitandreadtheplaytogetherforthreeorfourdaysbeforerehearsingit.
最新回复
(
0
)