首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
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
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、accessing
B、calculating
C、counting
D、measuring
答案
D
解析
转载请注明原文地址:https://kaotiyun.com/show/QHxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在系统转换的过程中,旧系统和新系统并行工作一段时间,再由新系统代替旧系统的策略称为(19);在新系统全部正式运行前,一部分一部分地代替旧系统的策略称为(20)。
数据存储在磁盘上的排列方式会影响I/O服务的总时间。假设每磁道划分成10个物理块,每块存放1个逻辑记录。逻辑记录R1,R2,…,R10存放在同一个磁道上,记录的安排顺序如下表所示:假定磁盘的旋转速度为20ms/周,磁头当前处在R1的开始处。若系统顺序处
在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,“/”表示路径中的分隔符,“/”在路径之首时表示根目录。图中,(10)。假设当前目录是D1,进程A以如下两种方式打开文件f1。①fd1=open("(11)/f1",o_R
SNMPv1的管理信息结构定义的应用数据类型time ticks的单位是(44)。
Linux系统在默认情况下将创建的普通文件的权限设置为(32)。
假设模拟信号的最高频率为5MHz,采样频率必须大于(14),才能使得到的样本信号不失真,如果每个样本量化为256个等级,则传输的数据速率是(15)。
DHCP协议的功能是(40)。在Linux中提供DHCP服务的程序是(41);DHCP服务将主机的MAC地址和IP地址绑定在一起的方法是在(42)文件中添加"host主机名{hardwareEthernetxx.xx.xx.xx.xx.xxfixe
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
某公司为便于远程员工在家里访问公司的一些数据,允许员工通过Internet访问公司的FTP服务器,如图5-1所示。为了能够方便地实现这一目标,决定在客户机与FTP服务器之间采用(31)协议,可在传输层对数据进行加密以保证数据通信的安全性。
现代计算机体系结构的发展突破了冯.诺依曼的体系结构,主要表现在(61)。多机系统与多计算机构成的计算机网络差别的主要特征是(62)。面向对象程序设计以(63)为基本的逻辑构件,用(64)来描述具有共同特征的一组对象,以(65)为共享机制,共享类中的方法和数
随机试题
KeyJames,SecretaryofHealthandHumanResourcesintheVirginiaStategovernment,lovestoturnthetablesonthosewhodon’t
门静脉高压症的治疗,错误的是
女,56岁,冬天煤炉取暖过夜。清晨被家人发现昏迷不醒急送医院。查体:口唇呈樱桃红。对诊断最有帮助的检查是
在碾压混凝土坝施工时,卸料、平仓、碾压中的质量控制,主要应保证()。
将现金送存银行,应填制的记账凭证是()。
供给弹性
对欧盟纺织品出口专用产地证(EEC产地证)由商务部签发,而不是由贸促会签发。()
决定再投资收益的主要因素有()。
Man:WouldyouliketogowithmetotheairporttopickupFrank?Woman:I’dliketo,butIhaveclasstill2:00.AndIkno
MillionsofAmericansareenteringtheir60sandaremoreconcernedthaneveraboutretirement.Theyknowtheyneedtosave,but
最新回复
(
0
)