The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a

admin2009-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)

The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a

软件设计师上午基础知识考试

软考中级

某开发人员不顾企业有关保守商业秘密的要求，将其参与该企业开发设计的应用软件的核心程序设计技巧和算法通过论文向社会发表，那么该开发人员的行为(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)。

某计算机系统中的进程在“就绪”、“运行”和“等待”三种状态之间转换，进程不可能实现(62)的状态转换。

Inlow-speednetwork,itisusuallyadequatetowaitforcongestiontooccurandthenreacttoitbytellingthesourceofpacke

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

治疗黄体功能不全月经先期脾气虚证，首选

患者男，72岁，下肢瘫痪，近期发现其骶尾部呈紫红色，皮下有硬结和水疱，该临床表现是压疮的

下列各项属于流动资产的是(　　)。

引起有关经济主体发生账面损失的汇率风险是()。

对附有回售条款的可转换公司债券持有人而言，当标的公司股票价格在一段时间内连续低于转股价格达到一定幅度时，把债券卖回给债券发行人，将有利于保护自身的利益。()

会议主持人主持会议的方法要从()，这两方面来理解。

使用VC++6．0打开考生文件夹下的源程序文件3．cpp。其中定义的类不完整，按要求完成下列操作，将类的定义补充完整。(1)基类People完成打印功能，定义其中的打印函数为虚函数，请在注释1后添加适当的语句。(2)类Boy继承于Peo

ManypeopleWentshoppingyesterday.ThereWereManypeople______yesterday.

The notion of NP-completeness has provided a(66)mathematical definition for(67)intractability of NP problems. But this measure a

软件设计师上午基础知识考试

软考中级

某开发人员不顾企业有关保守商业秘密的要求，将其参与该企业开发设计的应用软件的核心程序设计技巧和算法通过论文向社会发表，那么该开发人员的行为(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)。

某计算机系统中的进程在“就绪”、“运行”和“等待”三种状态之间转换，进程不可能实现(62)的状态转换。

Inlow-speednetwork,itisusuallyadequatetowaitforcongestiontooccurandthenreacttoitbytellingthesourceofpacke

OneofthedifficultiesinbuildinganSQL-likequerylangefortheWebistheabsenceofadatabaseschemaforthishuge,heter

治疗黄体功能不全月经先期脾气虚证，首选

患者男，72岁，下肢瘫痪，近期发现其骶尾部呈紫红色，皮下有硬结和水疱，该临床表现是压疮的

下列各项属于流动资产的是( )。

引起有关经济主体发生账面损失的汇率风险是()。

对附有回售条款的可转换公司债券持有人而言，当标的公司股票价格在一段时间内连续低于转股价格达到一定幅度时，把债券卖回给债券发行人，将有利于保护自身的利益。()

会议主持人主持会议的方法要从()，这两方面来理解。

使用VC++6．0打开考生文件夹下的源程序文件3．cpp。其中定义的类不完整，按要求完成下列操作，将类的定义补充完整。(1)基类People完成打印功能，定义其中的打印函数为虚函数，请在注释1后添加适当的语句。(2)类Boy继承于Peo

ManypeopleWentshoppingyesterday.ThereWereManypeople______yesterday.

The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a

Traditional　Internet　access　methods　like　dial-up　were　so　slow　that　host　computers　were　connected　to　the　dial-up(71)at　the　custom

下列各项属于流动资产的是(　　)。