题目内容

以下是NP完全问题的（）

A. 0-1背包
B. 顶点覆盖
C. 最短路
D. 最大公因子

查看答案

搜索结果不匹配？点我反馈

更多问题

P类问题可以（）

A. 多项式时间计算
B. 指数时间计算
C. 指数时间验证

下面属于NP完全问题的是（）

A. SAT
B. 最大独立集
C. 最小顶点覆盖
D. 旅行商问题

以下关于判定问题难易处理的叙述中错误的是（）。

A. 可以由多项式时间算法求解的问题是难处理的
B. 需要超过多项式时间算法求解的问题是易处理的
C. 可以由多项式时间算法求解的问题是易处理的
D. 需要超过多项式时间算法求解的问题是不能处理的

NP完全问题的证明方法有（）

A. 局部替换
B. 分支设计
C. 限制技术
D. 定义法