决定性问题

✍ dations ◷ 2025-04-03 17:12:55 #决定性问题
在可计算性理论与计算复杂性理论中,所谓的决定性问题(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’”,亦即“我们将无从得之”。需要了解更多信息请参见大卫·希尔伯特和停机问题。

相关

  • 白介素-1结构 / ECOD介白素-1包括11种细胞因子,在机体控制免疫和炎症反应中具有重要作用。这些细胞因子的发现始于1943年至1948年间,Menkin和Beeson对兔子腹腔细胞释放的致热原蛋白质
  • 聚酮聚酮(英语:Polyketides)是一类由细菌、真菌、植物与动物所生产出来的次级代谢产物,这类物质对生物的发育生长而言非必要,但可用于防卫或细胞间的沟通。聚酮是源自乙酰基(acetyl)与
  • 甲烷生成产甲烷作用,又称甲烷生成,指合成甲烷是微生物代谢的重要的和广泛的形式。可以生成甲烷的微生物称作产甲烷菌(英语:Methanogen)。这些微生物都属于原核生物中的古菌域,这是在系统发
  • 子宫子宫,中医学常称胞宫,又称女子胞,是中医的奇恒之腑之一。位于小腹正中,膀胱之后,直肠之前,下口连接阴道,为女性发生月经和孕育胎儿的器官。子宫是雌性哺乳动物的生殖器官中,用来让胚
  • 疾病患者患者,又称病人、病者和病患,是指医疗服务的接受者,大多用来指罹患疾病、或身体受到创伤,而需要医生和护理人员进行治疗的人;动物如遇到相同状况,也可以患者称之。但是对于不用接受
  • 哌嗪哌嗪(音:派秦(pài qín)。英语:Piperazine)是一种有机化合物。哌嗪是包含两个氮原子的六元杂环,两个氮原子处于对位。很多哌嗪类化合物有一些重要的药理性质,其都包含哌嗪官能团
  • 雨夹雪雨夹雪(sleet),又称作霙(汉语拼音:yīng,注音:ㄧㄥ,音同“英”)、夹冰丸,是雪和雨一同降下的现象。与液态的冻雨不同,以及与颗粒坚硬的冰珠不同,雨夹雪降下的颗粒柔软,呈半透明。由于雪花
  • 陈文泰县陈文泰县(越南语:Huyện Trần Văn Thời),又译作“陈文时县”,是越南金瓯省下辖的一个县。陈文泰县是金瓯省革命烈士陈文泰的故乡。该县即以陈文泰的名字命名。陈文泰县下辖2市
  • 中国图书馆分类法中国图书馆分类法(第5版)(在第3版原名是中国图书馆图书分类法),是中国大陆最通用的图书分类法。简称中图法。1971年北京图书馆(现中国国家图书馆)等36个单位组成编辑组开始编制,1973
  • 归纳推理归纳法或归纳推理(Inductive reasoning),有时叫做归纳逻辑,是论证的前提支持结论但不确保结论的推理过程。它基于对特殊的代表(token)的有限观察,把性质或关系归结到类型;或基于对反