单选题
NP类语言在图灵机下的定义为（）
发布日期：2021-06-18
NP={L∣L是一个能在非多项式时间内被一台NDTM所接受的语言}
NP={L∣L是一个能在非多项式时间内被一台DTM所接受的语言}
NP={L∣L是一个能在多项式时间内被一台DTM所接受的语言}
NP={L∣L是一个能在多项式时间内被一台NDTM所接受的语言}
试题解析
非确定性多项式难题
NP(Nondeterministic Polynomially，非确定性多项式)类问题是指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。NP类问题数量很大，如完全子图问题、图着色问题、旅行商(TSP)问题等。在P和NP问题中，P的难度最低，NP由于只对验证答案的时间作了限定，从而有可能包含某些无法在多项式时间内找到答案的问题，即NP是比P更困难的问题。
- 中文名
- 非确定性多项式难题
- 简称
- NP问题
- 相关概念
- P问题，NPC问题等
- 外文名
- Nondeterministic Polynomially problem
- 举例
- 完全子图问题、旅行商问题等
图灵机
图灵机，又称图灵计算机指一个抽象的机器，是，英国数学家艾伦・麦席森・图灵(1912―-1954年)于1936年提出的一种抽象的计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
- 中文名
- 图灵机
- 提出时间
- 1936年
- 外文名
- Turing Machine
- 别名
- 图灵计算
下的
下的，汉语词语，读音是xià de，意思是忍心。马致远《耍孩儿·借马》套曲:“没道理没道理,忒下的忒下的。恰才说来的话君专记,一口气不违借与了你。”
- 中文名
- 下的
- 解释
- 犹忍心
- 拼音
- xià de
题王网让考试变得更简单
扫码关注题王，更多免费功能准备上线！
此试题出现在
其他考试
在通常情况下（）
电路的故障有断路、短路、搭铁或额外电压降。（）
北京交大微联公司的JD－1A型双机热备结构的计算机联锁系统和关键部件采用的是（）
典型造釉细胞瘤X线片的特点（）
丁某，患肺结核l年有余，曾予化疗药物，现请中医治疗。症见咳嗽无力，气短声低，咳痰清稀，色白，量较多，偶或咯血，血色淡红，午后潮热，伴有畏风怕冷，自汗与盗汗并见，纳少神疲，便溏，面白，舌质光淡，边有齿印，苔薄，脉细弱而数。辨证为（ ）
扳动ZD6道岔时烧熔断器有哪些主要原因？如何处理？
我国预算年度的起止时间是每年的（ ）。
电阻应变片的（）是主要元件。
要素饮食不含有（ ）
关于中国经济改革，下列说法正确的是（）。