首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
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
42
问题
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
软件设计师上午基础知识考试
软考中级
相关试题推荐
某开发人员不顾企业有关保守商业秘密的要求,将其参与该企业开发设计的应用软件的核心程序设计技巧和算法通过论文向社会发表,那么该开发人员的行为(8)。
下图为某系统集成项目的网络工程计划图,从图可知项目最短工期为(69)天,至少需要投入(70)人才能完成该项目(假设每个技术人员均能胜任每项工作)。
局域网中某主机的IP地址为172.16.1.12/20,该局域网的子网掩码为(52),最多可以连接的主机数为(53)。
Traditional Internet access methods like dial-up were so slow that host computers were connected to the dial-up(71)at the custom
立即寻址方式中,数据放在(22)。
在实现文件系统时,为加快文件目录的检索速度,可利用“文件控制块分解法”。假设目录文件存放在磁盘上,每个盘块512字节。文件控制块占64字节,其中文件名占8字节,文件内部号和文件其他描述信息占56字节。设某一目录文件共有254个文件控制块,采用分解法前查找该
传统的交换机作为第二层设备,只能识别并转发(26)地址,要支持VLAN间的通信只能借助于具有(27)功能的网络设备。具有这种功能的设备有路由器和三层交换机。当用路由器解决VLAN通信时,路由器得到一个VLAN包后,根据目的IP地址,获得目的MAC地址及相应
某计算机系统中的进程在“就绪”、“运行”和“等待”三种状态之间转换,进程不可能实现(62)的状态转换。
Inlow-speednetwork,itisusuallyadequatetowaitforcongestiontooccurandthenreacttoitbytellingthesourceofpacke
OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter
随机试题
治疗黄体功能不全月经先期脾气虚证,首选
患者男,72岁,下肢瘫痪,近期发现其骶尾部呈紫红色,皮下有硬结和水疱,该临床表现是压疮的
背景某施工单位承担一机电工程项目设备安装。一台大型压缩机组到货后短时间不能进行安装,建设单位在未拆开压缩机包装的情况下,将压缩机机组运至施工单位工程的临时库房,交与施工单位管理。施工过程中,由于建设单位需要使用这个临时库房所占用地,要求施工单位拆
下列各项属于流动资产的是( )。
引起有关经济主体发生账面损失的汇率风险是()。
对附有回售条款的可转换公司债券持有人而言,当标的公司股票价格在一段时间内连续低于转股价格达到一定幅度时,把债券卖回给债券发行人,将有利于保护自身的利益。()
会议主持人主持会议的方法要从(),这两方面来理解。
根据下列资料。回答问题。2016年,我国邮政行业业务总量完成7397.2亿元,同比增长45.7%。全年邮政行业业务收入(不包括邮政储蓄银行直接营业收入)完成5379.2亿元,同比增长33.2%。快递业务实现快速增长,全年快递服务企业业务量完成312.8
使用VC++6.0打开考生文件夹下的源程序文件3.cpp。其中定义的类不完整,按要求完成下列操作,将类的定义补充完整。(1)基类People完成打印功能,定义其中的打印函数为虚函数,请在注释1后添加适当的语句。(2)类Boy继承于Peo
ManypeopleWentshoppingyesterday.ThereWereManypeople______yesterday.
最新回复
(
0
)