首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
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
30
问题
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、relaxed
B、rough
C、rigorous
D、feasible
答案
C
解析
转载请注明原文地址:https://jikaoti.com/ti/JSa7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在下图的网络配置中,总共有(32)个广播域,(33)个冲突域。
页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为4K,地址变换过程如下图所示,图中逻辑地址用十进制表示。图中有效地址经过变换后,十进制物理地址a应为(17)。
通常路由器不进行转发的网络地址是(46)。
在异步通信中,每个字符包含1位起始位、7位数据位、1位奇偶位和2位终止位,若每秒钟传送100个字符,采用4相相位调制,则码元速率为(16),有效数据速率为(17)。
使用CIDR技术把4个网络100.100.0.0/18、100.100.64.0/18、100.100.128.0/18和100.100.192.0/18汇聚成一个超网,得到的地址是(53)。
在实现文件系统时,为加快文件目录的检索速度,可利用“文件控制块分解法”。假设目录文件存放在磁盘上,每个盘块512字节。文件控制块占64字节,其中文件名占8字节,文件内部号和文件其他描述信息占56字节。设某一目录文件共有254个文件控制块,采用分解法前查找该
在MIB-2功能组的接口组中,如果对象ifAdminStatus的值为up(1),而ifOperStatus的值为down(2),则该接口的状态为(38)。
传统的交换机作为第二层设备,只能识别并转发(26)地址,要支持VLAN间的通信只能借助于具有(27)功能的网络设备。具有这种功能的设备有路由器和三层交换机。当用路由器解决VLAN通信时,路由器得到一个VLAN包后,根据目的IP地址,获得目的MAC地址及相应
OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter
软件设计中划分模块的一个准则是(61)。两个模块之间的耦合方式中,(62)耦合的耦合度最高,(63)耦合的耦合度最低。一个模块内部的内聚种类中,(64)内聚的内聚度最高,(65)内聚的内聚度最低。
随机试题
在肺癌放射治疗中,照射剂量超过多少时,可出现第二次食管炎
乳牙活髓切断的适应证
合同分析的内容中,关于合同价格的内容还应包括计价方法和()。
市场营销组合的策略包括()。
保理虽然是一种综合性的金融服务方式,但其同单纯的融资或收款管理没有本质区别。()
在细节测试中,可接受的误受风险与样本数量之间是()变动关系。
物价上涨就是通货膨胀。()
若有以下语句,则正确的描述是()。staticcharX[]="12345";staticchary[]=[’1’,’2’,’3’,’4’,’5’,’\0’};
《经济之声.央广财经评论》报道,近些年中国心理疾病呈高发态势,有专家认为这是一种公民焦虑症,中国正在进入全民焦虑的时代,调查表明随着社会竞争的加剧,焦虑正逐渐成为一种普遍的心态,在许多人看来身边往往危机四伏,总有原因让人感到不安。然而有专家却称全民焦虑是中
HarvardPresident’sAddress:aDifferentLife1.Students’wonderWhat【T1】wouldbelike【T1】______2.Whatshouldstudentsunder
最新回复
(
0
)