题目内容

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

A. 最大公约数
B. 排序问题
C. 二维匹配问题
D. 完全子图问题

查看答案

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

更多问题

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

A. 完全子图问题
B. 旅行销售问题
C. 排序问题
D. 图的着色问题

以下哪个器件不是计算的工具?_______

A. 算盘
B. 计算器
C. 计算机
D. 图灵机

()在1936年证明,图灵机的停机问题是不可判定的。

A. 图灵
B. 冯.诺依曼
C. 哥德尔
D. 厄布朗

非确定性图灵机和确定性图灵机的区别是:在给定状态和输入时,其行为将________。

A. 不确定
B. 唯一确定
C. 不知道
D. 以上都不对