决定性问题

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

相关

  • 透镜本条目介绍的是光学设备,其他领域的透镜不在此处讨论。透镜是一种将光线聚合或分散的设备,通常是由一片玻璃构成,但用于其他电磁辐射的类似设备通常也称为透镜,例如:由石蜡制成的
  • 氧氟沙星氧氟沙星(氟嗪酸, Ofloxacin)是一种人工合成、广谱抗菌的氟喹诺酮类药物。氧氟沙星合成于1982年,口服易吸收,快而完全,血药浓度高而持久,药物体内分布广。此抗生素适合做为最后一线
  • 社会经济学社会经济学(英语:Socioeconomics),是研究经济活动如何影响和社会过程塑造的社会科学。一般来说,它分析一个社会如何因地方或区域经济或全球经济而进步、或是停滞、甚至退化。社
  • 黑棘皮症黑色棘皮症(拉丁语: Acanthosis nigricans),又名棘皮症、黑棘皮症、棘皮病等,常伴有肥胖的一种皮肤病变。属副肿瘤性疾病、先天性/发育性病症,病发部位多于皮肤、皮下、外分泌、
  • 拉贾斯坦邦拉贾斯坦邦(印地语:राजस्थान,拉丁字母转写:Rajasthan)位于印度西部,与巴基斯坦相接壤,是印度境内的一个邦。该邦官方语言是拉贾斯坦语而除此之外包括信德语、古吉拉特语和
  • 免疫能力贫弱免疫缺陷(英语:immunodeficiency)是指免疫系统抵抗传染病的能力失常或欠缺。免疫缺陷还可能降低肿瘤免疫监视功能。免疫缺陷多为继发性(secondary)免疫缺陷,不过也有些人生来就有
  • 亚历珊德拉·厄巴科扬亚历山德拉·阿萨诺芙娜·埃尔巴金(俄语:Алекса́ндра Аса́новна Элбакя́н;1988年11月6日-)是一位哈萨克斯坦籍研究生、 计算机程序员以及Sci-Hub的
  • 胎儿窘迫胎儿窘迫(fetal distress),是胎儿宫内缺氧的医学上统称,是一种综合症状。当胎儿的心跳变慢,并且于子宫收缩后保持缓慢,这表示婴儿无法得到足够的氧气。此情况并非罕见,根据医学研究
  • 核酸内切酶核酸内切酶(英语:endonuclease)在核酸水解酶中,为可水解分子链内部磷酸二酯键生成寡核苷酸的酶,与核酸外切酶相对应。从对底物的特异性来看,可分为DNaseⅠ、DNaseⅡ等分解DNA的酶;R
  • 正写法正写法,即是文字符号形体的规范和使用规则,包括正字法和正词法。汉字正字法可依据《通用规范汉字表》、《简化字总表》、修订后的《第一批异体字整理表》、《现代汉语通用字表