决定性问题

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

相关

  • 围产期产前(Prenatal)或产前发育(Prenatal development)是人类胚胎或胎儿在孕期的孕育过程,从受精,至诞生。通常,也可使用术语胚胎发育、胎儿发育,或胚胎学来表示。胚胎发育始于受精。
  • 丝足虫类丝足虫门是一类原生动物,属于有孔虫界. 也有人主张丝足虫独立为一界.丝足虫的主要特征是通过丝状伪足摄食,没有真实的胞口。
  • 管理水管理是在水文政策与法律之下对于水资源的计划、开发、分配、运输以及适当利用的过程。它有以下几种含意:
  • Betamethasone倍他米松(Betamethasone)为一固醇类药物,可用于治疗多种风湿免疫性疾病,如类风湿性关节炎、全身性红斑狼疮,以及皮肤炎和银屑病等等免疫性皮肤疾病。其他适应症还包含哮喘及血管
  • 喹唑啉喹唑啉(Quinazoline)是一种杂环化合物,化学式C8H6N2,由一个苯环与一个嘧啶环稠合而成。喹唑啉也可看做萘环的两个CH被N原子替换,这样的结构称为萘啶。喹唑啉及其衍生物的典型制备
  • 廊开府廊开府(泰语:จังหวัดหนองคาย,皇家转写:Changwat Nong Khai,泰语发音:)为泰国东北部之一个府。该府原名为“曼派村”,原属老挝的“万象城”统治。拉达那哥欣王国时代,该
  • 底比斯圣队底比斯圣队(古希腊语 Ιερός Λόχος , hieròs lókhos)是古希腊城邦底比斯的一支精锐部队,共300人,由150对“古希腊少年爱”伴侣组成。这支部队是前4世纪底比斯军队的精
  • 硕世生物硕世生物(上交所:688399),全称是江苏硕世生物科技股份有限公司,是一家中国生物技术公司。董事长为房永生。2010年4月12日成立于江苏泰州。主要控股股东为闰康生物,主要产品为体外
  • 戒断症状药物戒断(英语:drug withdrawal),一种因为停止药物治疗,或停止娱乐性药物、烟草、酒精的服用,而产生的综合症(symptoms)。在产生物质依赖的现象后,突然停止服用药物,在12至48小时内就
  • 操作语义学操作语义学是计算机科学中的一个概念,它是使得计算机程序在数学上更加严谨的一种手段。其它类似的手段包括提供形式语义学,包括公理语义学和指称语义。一个计算机语言的操作语