2. 计算机
  3. 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

admin2009-02-15  28
问题 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://kaotiyun.com/show/LHxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

相关试题推荐
随机试题
最新回复(0)