[单选题]

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

参考答案与解析：

相关试题

( ) from one phase are usually reviewed for completeness and accuracy and approved before work start

[单选题]( ) from one phase are usually reviewed for completeness and accuracy and a

  • 查看答案

    • Parents in China still cherish the notion that the only way out for their children is to enter colle

    [单选题]Parents in China still cherish the notion that the only way out for their c

  • 查看答案

    • The term “plant neurobiology” was around the notion that some aspects of plant behavior could be t

    The term “plant neurobiology” was around the notion that some aspects of plant

  • 查看答案

    • This goes against the notion most people hold that as we age, environmental influences gradually ove

    This goes against the notion most people hold that as we age, environmental infl

  • 查看答案

    • 根据以下代码， 得到的结果为？ import numpy as np a=np.arange(10).reshape(2,5).T b=np.arange(20).reshape(5,4) c=np

    根据以下代码， 得到的结果为？ import numpy as np a=np.arange(10).reshape(2,5).T b=np.arange(2

  • 查看答案

    • NP完全问题

    [名词解释] NP完全问题

  • 查看答案

    • 1Np=（）dB。

    [单选题]1Np=（）dB。A . 7.01B . 8.868C . 9.025D . 10.14

  • 查看答案

    • NP and ( ) are essential components of a sentence.

    [单选题]NP and ( ) are essential components of a sentence.A.VPB.PPC.APD.all of the

  • 查看答案

    • NP and ( ) are essential components of a sentence.

    [单选题]NP and ( ) are essential components of a sentence.A.VPB.PPC.APD.all of the

  • 查看答案

    • NP and ( ) are essential components of a sentence.

    [单选题]NP and ( ) are essential components of a sentence.A.VPB.PPC.APD.all of the

  • 查看答案