logo - 刷刷题
下载APP
【单选题】

P类问题:由确定型图灵机在多项式时间内可解的一切判定问题所组成的集合,下面哪个不是P类问题?________

A.
最大公约数
B.
排序问题
C.
二维匹配问题
D.
完全子图问题
题目标签：多项式时间确定型图灵机判定问题
举报
如何制作自己的在线小题库
参考答案：
参考解析：
.
刷刷题刷刷变学霸
举一反三

【单选题】P类问题:由确定型图灵机在多项式时间内可解的一切判定问题所组成的集合,下面哪个不是P类问题?________
A.
最大公约数
B.
排序问题
C.
二维匹配问题
D.
完全子图问题
查看完整题目与答案

【判断题】NP问题是指用非确定性算法在多项式时间内解决的问题。()
A.
正确
B.
错误
查看完整题目与答案

【判断题】判定问题的近似解是指:输入满足某种性质或近似满足某种性质。()
A.
正确
B.
错误
查看完整题目与答案

【简答题】【名词解释】多项式时间度
查看完整题目与答案

【简答题】什么是多项式时间近似方案（PTAS）？什么是完全多项式时间近似方案（FPTAS，FPAS）？
查看完整题目与答案

【判断题】EXP 类是所有指数时间可解的判定问题组成的问题类
A.
正确
B.
错误
查看完整题目与答案

【简答题】能够在多项式时间内被一台 DTM 接受的一类问题统称为 。
查看完整题目与答案

【单选题】下面关于判定问题难易处理的叙述中正确的是
A.
可以由多项式时间算法求解的问题是易处理的
B.
可以由多项式时间算法求解的问题是难处理的
C.
需要超过多项式时间算法求解的问题是易处理的
D.
需要超过多项式时间算法求解的问题是不能处理的
查看完整题目与答案

【多选题】下列问题中计算复杂度高于多项式时间复杂度的有（）。
A.
整数因子分解
B.
哈密顿回路问题
C.
最小生成树问题
D.
离散对数问题
查看完整题目与答案

【多选题】以下关于判定问题难易处理的叙述中错误的是
A.
可以由多项式时间算法求解的问题是易处理的
B.
需要超过多项式时间算法求解的问题是易处理的
C.
可以由多项式时间算法求解的问题是难处理的
D.
需要超过多项式时间算法求解的问题是不能处理的
查看完整题目与答案