首页 >
决定性问题
✍ dations ◷ 2025-08-19 06:27:41 #决定性问题
在可计算性理论与计算复杂性理论中,所谓的决定性问题(Decision problem)是一个在某些形式系统回答是或否的问题。例如:“给两个数字x与y,x是否可以整除y?”便是决定性问题,此问题可回答是或否,且依据其x与y的值。决定性问题与功能性问题(Function problem,或复杂型问题)密切相关,功能性问题的答案内容,较简单的是与非复杂许多。范例问题:“给予一个正整数x,则哪些数可整除x?”另一个与上述两类问题相关的是最佳化问题(Optimization problem),此问题关心的是寻找特定问题的最佳答案。解决决定性问题的方法称为决策程式或算法。一个针对决定性问题的算法将说明给予参数x和y的情况下如何决定x是否整除y。若是某些决定性问题可以被一些算法所解决,则称此问题可决定。计算复杂度的领域中,分类可决定问题的依据在于此问题有多难被解决。在此标准下,所谓的难是以解决某问题最有效率的算法所花费的计算资源为依据。在递回理论中,非决定性问题由图灵度决定,指的是一种在任何解答中隐含的不可计算性量词。计算性理论的研究集中在决定性问题上。在与功能性问题的等值问题中,并没有失去其普遍性。决定性问题指的是在一个数量为无限大的输入集合中,可产出任何是或非解答的问题之集合。因此传统上定义决定性问题,乃依其解答为是的输入之集合。在此情形下,一决定性问题亦等于一形式语言。形式上,决定性问题是一自然数子集A。借由使用哥德尔数,也可学习诸如形式语言的其他集合。非正规的定义决定性问题,就是判别一个给予的数字是否在此集合内。一决定性问题若其A是一个递归集合,则称做可决定的(decidable)或有效可解(effectively solvable)。若其A是一递归可枚举集合则称为部分可决定的(partially decidable)、半可决定的(semidecidable)、可解的(solvable)或可证明(provable)。除此之外,此问题称为不可决定的。一个经典可决定的决定性问题是质数问题。借由测试每一个可能的因数,有可能有效决定一个自然数是否为质数。尽管存在很多效能更佳的质数判定方法,任何有效方法的存在就已足够建立可决定性。重要的不可决定的决定性问题包括停机问题,其他请见不可决定的问题列表。在计算复杂性理论中,完备的决定性问题通常用来判别其他决定性问题的复杂度类别。重要的实例包括SAT问题与其数变种,还有无向与有向图可达性问题。德语“Entscheidungsproblem”,亦即“判定性问题”(Decision-problem),最早出自于大卫·希尔伯特的话:“在1928年的会议上,希尔伯特精确地描述了他的问题。首先,数学是否具有完备性?……其次,数学是否具有相容性?……再次,数学是否具有判定性?这些问题的意思是,是否存在这样一种确定的方法,在理论上可适用于任何假设,并且能够保证对无论是否正确的假设都能给出一个正确的结果”(Hodeges,p. 91)。希尔伯特相信“在数学上没有‘ignorabimus’”,亦即“我们将无从得之”。需要了解更多信息请参见大卫·希尔伯特和停机问题。
相关
- 病理学人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学病理学(pathology)是医学领域的一门分支
- 种系发生现代生物分类群体从它们的 共同祖先遗传分化的图示。进化论介绍(英语:Introduction to evolution) 演化的证据 共同起源 共同起源的证据群体遗传学 · 遗传多样性 突变 · 自
- 细菌性痢疾志贺杆菌病(Shigellosis),也称为杆菌性痢疾(bacillary dysentery)、细菌性痢疾,是一种传染病,因为摄食了遭志贺氏菌污染的食物或饮水,引发食物中毒。特征是出血性腹泻。志贺氏菌是一
- 多萝西·克劳福特·霍奇金多萝西·玛丽·霍奇金,OM,FRS(英语:Dorothy Mary Hodgkin,1910年5月12日-1994年7月29日)本姓克劳福特(Crowfoot),英国女性生物化学家,促进了蛋白质晶体学的发展。她生于开罗,1964年获诺
- 新美鞭菌门新美鞭菌门是厌氧性真菌的一门,发现于食草动物的消化道中。它只包括一纲、一目、一科,目前已知6属。新美鞭菌门的真菌为Orpin于1975年首次根据绵羊的瘤胃中发现的运动细胞所描
- 花柳性淋巴肉芽肿花柳性淋巴肉芽肿,是一种由砂眼披衣菌引起的性病,特别盛行于亚、热带地区。其男性患者远多于女性患者。淋巴肉芽肿症状经过1-3周的潜伏期后,受感染患处(通常是性器官)会出现一个
- 乌泰他尼府乌泰他尼府(泰语:จังหวัดอุทัยธานี,皇家转写:Changwat Uthai Thani,泰语发音:),在泰国北部,他的邻府自北顺时针是那空沙旺府、猜纳府、素攀府、北碧府和达府。华人称
- 手肘肘是指手臂中部,连接上臂与前臂的铰链关节——肘关节附近的区域。有三块骨头与肘关节相连:上臂的肱骨、前臂的尺骨和桡骨。肘尖的突出物是尺骨鹰嘴,而肘内部的外表构造称为肘前
- 杓状软骨杓状软骨(arytenoid cartilage、arytenoid、/ærᵻˈtiːnɔɪd/)是一对小三角锥体,形成喉部的一部分,且声带(vocal cords)与之相连。这些相连的结构允许及帮助声带的运动。每个
- 临时工临时工(英语:temporary worker)又称散工,泛指在工作场所里非正式雇用的劳工,通常以日薪计酬。也不像正式劳工能够享有退休金与每月最低工资的保障。临时工又分成约聘雇员与人力派