你可能感兴趣的试题

单项选择题

下列关于作家苇岸的信息错误的一项是：（）

A.1960年1月生于北京昌平县北小营村
B.1999年5月写出最后一则《二十四节气：谷雨》之后因病去世
C.他评价梭罗的文字是“有机”的，说他的“文字本身仿佛是活的，富于质感和血温”
D.苇岸初入文坛，即以写作散文为主

单项选择题

在“证比求易算法”中，对公主给出的数进行验证，显然是在多项式时间内可以解决的问题，因此，这类问题属于NP类问题。现在，P=NP是否成立的问题是计算学科和当代数学研究中最大的悬而未决的问题之一。2000年5月，美国克莱数学研究所（The Clay Institute of Mathematics）提供100万美元求解这一问题。下面论述错误的是（）‌

A.库克（S.A.Cook）等人认为NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，所有NP问题都是在多项式时间内可解的，这些问题被称为NP完全性问题。
B.库克因其在计算复杂性理论方面（主要是在NP完全性理论方面）的奠基性工作，于1982年获ACM图灵奖。
C.历史上第一个NP完全性问题是库克于1971年提出的可满足性问题。
D.若P≠NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。