首页 >
决定性问题
✍ dations ◷ 2025-07-03 13:44:24 #决定性问题
在可计算性理论与计算复杂性理论中,所谓的决定性问题(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’”,亦即“我们将无从得之”。需要了解更多信息请参见大卫·希尔伯特和停机问题。
相关
- 肺结核结核病(Tuberculosis,又称TB)为结核杆菌感染引起的疾病。结核通常造成肺部感染,也会感染身体的其他部分。大多数感染者没有症状,此型态感染称为潜伏结核感染(英语:Latent tuberculo
- 厌氧菌厌氧生物,或称厌气生物,是指一种不需要氧气生长的生物。它们大致上可以分为三种,即专性厌氧生物、兼性厌氧生物及耐氧厌氧生物 。人体内的厌氧生物多存在于消化系统中,有些种类
- 骨盆检查骨盆检查(又称骨盆腔检查、盆腔检查、内诊或是妇科检查),为妇产科中最基本的身体检查。其可粗略分为外部的检查和内部的检查两部分,内部检查于英文中又可称作“双手触诊”或是“
- 咽喉炎咽喉痛(sore throat、throat pain,又称喉咙痛或喉痛),是指咽喉出现痛楚的症状,最主要的成因是咽喉炎(喉咙发炎),但可由其他原因引致,例如白喉和伤风感冒威胁。 服用非类固醇消炎止痛
- 空军美国空军(英语:United States Air Force,缩写:USAF)是美国军队中的空军军种。其任务是“通过空中、外太空和网络空间中的武力保护美国及其利益”,它于1947年9月18日正式成立。美国
- 积雨云积雨云(拉丁语:Cumulonimbus,符号:Cb),又名雷雨云,属于直展云族。积雨云可以单独从积云状态发展出来,也可能是伴随冷锋面产生的,通常会产生强阵性的降水,并伴有大风、雷暴等。积雨云是
- 单氟磷酸钠单氟磷酸钠,化学式Na2PO3F,缩写MFP。单氟磷酸钠是一种白色固体,饱和水溶液在25°C时含单氟磷酸钠42%。可从0°C水溶液中获得单氟磷酸钠十水合物,结晶水若用加热方式除去,则导致水
- 阿尔戈斯阿尔戈斯(希腊语:Άργος,英语:Argos),或译阿戈斯、阿哥斯、阿果斯,是希腊的一座城市,位于伯罗奔尼撒半岛的东北。阿尔戈斯有约5000年的历史,在它的历史上,古希腊人、罗马人、法兰
- 胎膜羊膜囊是两层坚韧、薄、透明的膜,位于羊膜动物的胎盘之内。装着发育中的胚胎(后来变成胎儿),直到出生前不久为止。内层的膜是装着羊水和胚胎的羊膜。外层膜绒毛膜包着羊膜,本身是
- 21人类的21号染色体是23对染色体的其中之一,正常状况下每个细胞拥有两条。此染色体是所有人类染色体中最小的一个,含有大约4700万个碱基对,占细胞内所有DNA的1.5%。21号染色体的