首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
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
68
问题
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
软件设计师上午基础知识考试
软考中级
相关试题推荐
某计算机系统的可靠性结构是如下图所示的双重串并联结构,若所构成系统的每个部件的可靠度均为0.9,即R=0.9,则该系统的可靠度为(3)。
如果两个交换机之间设置多条Trunk,则需要用不同的端口权值或路径费用来进行负载均衡。默认情况下,端口的权值是(55)。在如下图所示的配置下,(56)。
局域网中某主机的IP地址为172.16.1.12/20,该局域网的子网掩码为(52),最多可以连接的主机数为(53)。
下面的地址中,属于本地环路地址的是(53)。
某网络结构如下图所示。在Windows操作系统中,Server1通过安装(28)组件创建Web站点。PCI的用户在浏览器地址栏中输入www.abc.com后无法获取响应页面,管理人员在Windows操作系统下可以使用(29)判断故障发生在网络A内还是网络A
DHCP协议的功能是(40)。在Linux中提供DHCP服务的程序是(41);DHCP服务将主机的MAC地址和IP地址绑定在一起的方法是在(42)文件中添加"host主机名{hardwareEthernetxx.xx.xx.xx.xx.xxfixe
在某个支持SNMPv2MIB组的代理中,snmpSerialNo对象的当前值为2006。这时,该代理站同时收到两个管理站发来的set请求,这两个set请求的snmpSerialNo值都是2006,当代理站处理完这两个set请求后,其snmpSerialN
OSI网络管理标准定义了网管的5大功能。比如对每一个被管理对象的每一个属性设置阈值、控制阈值检查和告警的功能属于(51);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(52);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
The purpose of the requirements definition phase is to produce a clear, complete, consistent, and testable(6)of the technical re
随机试题
A.羊肠线B.丝线C.组织黏合剂D.不锈钢丝E.尼龙线血管吻合最合适的材料是
关于血清T3、T4测定的叙述错误的是
对早期肝硬化有确诊意义的检查是
生后21天男婴,证见面目发黄,色深晦暗,腹部胀满,右胁下可及痞块,质硬,神疲纳呆,小便黄,不易洗去,大便灰白,唇色暗红,舌苔黄。选方是
施工成本管理的措施中,( )是其他三类措施的前提和保障。
在调查操纵证券市场、内幕交易等重大证券违法行为时,经国务院证券监督管理机构主要负责人批准,一般可以限制被调查事件当事人的证券买卖不超过()个交易日。
企业以盈余公积向投资者分配现金股利,不会引起留存收益总额的变动。()
静止就是不运动。()
社会主义初级阶段基本路线的简明概括和主要内容是()。
假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为``
最新回复
(
0
)