可解性问题是指能够找到多项式时间复杂性算法进行求解的问题,难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。A.P类问题是可解性问题,NP类问题是难解性问题B.NP类问题不一定是难解性问题,因为P类问题也一定是NP类问题C.NP类问题不确定是否是P类问题,但NPC类问题一定是难解性问题D.上述说法有不正确的

可解性问题是指能够找到多项式时间复杂性算法进行求解的问题,难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。

A.P类问题是可解性问题,NP类问题是难解性问题

B.NP类问题不一定是难解性问题,因为P类问题也一定是NP类问题

C.NP类问题不确定是否是P类问题,但NPC类问题一定是难解性问题

D.上述说法有不正确的


参考答案和解析
解的存在性、唯一性和稳定性

相关考题:

背包问题贪心算法的时间复杂性。

快速排序算法的最坏时间复杂性和平均时间复杂性函数。

设求解某问题的递归算法如下:求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且Move为常数级算法,并设算法Move的计算时间为k,当n=5时,算法F的计算时间为(62)。A.7kB.15kC.31kD.63k

设求解某问题的递归算法如下: F(int n){ if n==1{ Move(1); } else{ F(n-1); Move(n); F(n-1); } } 求解该算法的计算时间时,仅考虑算法Move所进行的计算为主要计算,且Move为常数级算法,设算法Move的计算时间为k,当n=5时,算法F的计算时间为(42)。A.7kB.15kC.31kD.63k

算法的时间复杂性是指该算法包含 【】 的多少,它是一个算法运行时间的相对度量;一个算法的空间复杂性是指该算法在运行过程中临时占用的 【】 的大小。

一个算法的时间复杂性通常用数量级形式表示,当一个算法的时间复杂性与问题的规模n无关时,则表示为 【】

关于概率算法,下述说法中错误的是(15)。A.数值概率算法所求得的往往是近似解,且精度随着计算时间的增长而不断提高,常用于数值计算B.舍伍德算法能求得问题的一个解,但未必正确,正确的概率随着计算时间的增加而提高,通常用于求问题的精确解C.若能用拉斯维加斯算法求得一个解,那么它一定正确,其找到解的概率也随着计算时间的增加而提高D.蒙特卡罗算法的缺点就是无法有效地判断所求解的正确性

一个计算机算法是对特定问题求解步骤的一种描述。算法的( )是指算法能够对不合理数据及非法操作进行识别和处理的能力。A.有穷性B.可行性C.确定性D.健壮性

一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上,因此算法的复杂性有()复杂性和空间复杂性之分。

关于0-1背包问题以下描述正确的是()A、可以使用贪心算法找到最优解B、能找到多项式时间的有效算法C、使用教材介绍的动态规划方法可求解任意0-1背包问题D、对于同一背包与相同的物品,做背包问题取得的总价值一定大于等于做0-1背包问题

Prim算法利用()策略求解()问题,其时间复杂度是()。

对于0-1背包问题和背包问题的解法,下面()答案解释正确。A、0-1背包问题和背包问题都可用贪心算法求解B、0-1背包问题可用贪心算法求解,但背包问题则不能用贪心算法求解C、0-1背包问题不能用贪心算法求解,但可以使用动态规划或搜索算法求解,而背包问题则可以用贪心算法求解D、因为0-1背包问题不具有最优子结构性质,所以不能用贪心算法求解

在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型。3个基本计算模型是()、()、()。

动态规划算法的基本思想是将待求解问题分解成若干(),先求解(),然后从这些()的解得到原问题的解。

采用动态规划策略求解问题的显著特征是满足最优性原理,其含义是()。A、当前所作决策不会影响后面的决策B、原问题的最优解包含其子问题的最优解C、问题可以找到最优解,但利用贪心算法不能找到最优解D、每次决策必须是当前看来的最优决策才可以找到最优解

一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上,因此算法的复杂性有()复杂性和()复杂性之分。

算法的时间复杂性越好,可读性就越差;反之,算法的可读性越好,则时间复杂性就越差。

关于页面调度算法的3个条件、5个求解问题是什么?

算法是求解问题步骤的有序集合,它能够产生()并在有限时间内结束。A、显示B、代码C、过程D、结果

单选题关于0-1背包问题以下描述正确的是()A可以使用贪心算法找到最优解B能找到多项式时间的有效算法C使用教材介绍的动态规划方法可求解任意0-1背包问题D对于同一背包与相同的物品,做背包问题取得的总价值一定大于等于做0-1背包问题

单选题在下列关于计算机算法的说法中,不正确的是()A一个正确的算法至少要有一个输入B算法的改进,在很大程度上推动了计算机科学与技术的进步C判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D目前仍然存在许多涉及到国计民生的重大课题,还没有找到能够在计算机上实施的有效算法

填空题动态规划算法的基本思想是将待求解问题分解成若干(),先求解(),然后从这些()的解得到原问题的解。

问答题关于页面调度算法的3个条件、5个求解问题是什么?

单选题对于计算机求解问题,下列叙述正确的是()。A利用计算机进行问题求解,是用机器代替人,属于人工智能应用B计算机求解问题主要适用于自然系统,社会系统无法建模C计算机进行问题求解是利用了计算机运行速度快、精度高、自动化和不知疲倦的特性D只有通过计算机执行求解算法才能得到问题的解

单选题关于算法的时间复杂性,下列叙述正确的是()。A时间复杂性是衡量一个算法优劣的唯一标准B所有算法都与问题的规模有关,问题规模越大,时间复杂性越大C通常不能简单地以算法运行时间度量算法的时间复杂性D同一个算法可以编写为不同的程序,程序的执行时间不同,因此一个算法有多种不同的时间复杂性

填空题在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型。3个基本计算模型是()、()、()。

判断题算法的时间复杂性越好,可读性就越差;反之,算法的可读性越好,则时间复杂性就越差。A对B错

填空题Prim算法利用()策略求解()问题,其时间复杂度是()。