决定性问题

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

相关

  • 矿难矿难,指在采矿过程中发生的事故,通常造成伤亡的危险性极大。世界上每年至少有几千人死于矿难。矿难发生的频率在中国等发展中国家尤为突出。在2003年,中国生产了世界约35%的煤,
  • 液流电池液流电池(英语:Flow battery),一种蓄电池,在这个系统中,通常包含两个容器,其中储存着液体化学溶剂,形成两个次系统。这两个次系统间的连接部分,为发电区,以一个薄膜隔开。这两种化学溶
  • 弧状云弧状云(arcus cloud),是一种罕见的云层。通常会形成于冷锋之前缘,一旦寒冷的气流扩展开来,会推升前方的暖空气,气流有时会沿着水平轴方向流动。弧状云又可分为卷轴云(Roll clouds)和
  • 硝基硝基化合物是含有一个或若干个硝基官能团(-NO2)的有机化合物。硝基化合物通常易爆,尤其是当分子内含有超过一个硝基且不纯时。芳香硝基化合物通常通过硝化反应合成,即混合硝酸
  • 欧亚非大陆亚非欧大陆、亚欧非大陆或欧亚非大陆指的是亚洲、欧洲、非洲三个大陆的合称。在地理上,直到苏伊士运河开通以前,三个大陆是相连的。在文化上,欧洲、亚洲和北非的关系比较接近,特
  • 异维A酸异维A酸(Isotretinoin),是维A酸的异构体,最初是一种治疗脑癌、胰脏癌和皮肤癌等多种癌病的药物,但现时常用作治疗青春痘,通常为口服用A酸,外用A酸则通常为维A酸成分,有时亦用作医治
  • 苏丹红苏丹红是一种亲脂性偶氮化合物,作为人工合成的红色工业染料,被广泛用于如溶剂、油、蜡、汽油的增色以及鞋、地板等增光方面。苏丹红主要包括Ⅰ、Ⅱ、Ⅲ和Ⅳ四种类型。进入体内
  • 安东尼·弗契安东尼·弗契(Anthony S. Fauci,1940年12月24日-),美国医学研究者。他坚持不懈地努力追求精湛的研究,这对全世界抵抗H1N1甲型流感、艾滋病和其他传染病的斗争作出重大贡献。安东尼
  • 居礼夫妇居里可能指:
  • 瞳孔瞳孔(英语:Pupil)又称瞳神,是眼球血管膜的前部虹膜中心的圆孔。沿瞳孔环形排列的平滑肌叫瞳孔括约肌,收缩时使瞳孔缩小,沿瞳孔放射状排列的平滑肌叫瞳孔放大肌,松弛时使瞳孔放大,调