函式问题

在计算复杂性理论内，功能性问题或者函式问题（function problem）是一种计算问题（en:computational problem），我们对任何一种输入都预期会有单一个输出，但是输出不像是决定性问题一样这么单纯。换句话说，输出不只YES跟NO。重要的范例像是旅行推销员问题，询问一张图是否有可以绕过每一点的不重复路径（输出为路径），以及整数分解，输出为输入的质因数。

简介在计算复杂性理论内，功能性问题或者函式问题（function problem）是一种计算问题（en:computational problem），我们对任何一种输入都预期会有单一个输出，但是输出不像是决定性问题一样这么单纯。换句话说，输出不只YES跟NO。重要的范例像是旅行推销员问题，询问一张图是否有可以绕过每一点的不重复路径（输出为路径），以及整数分解，输出为输入的质因数。

因为没有明显类比的语言，功能性问题比起决定型问题要难以研究。而且因为输出的可能变多，在解决输入输出之间的转换，功能性问题归约的过程也比较微妙。功能性问题也可以用像是决定性问题的方式来分成各种复杂度类。举例来说FP是指可以用确定型图灵机在多项式时间里面可以解决的功能性问题（类似于决定性问题的P），而FNP是指可以用非确定型图灵机在多项式时间里面可以解决的功能性问题（类似于决定性问题的NP）。1

计算复杂性理论计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。

如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。

在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。1

决定性问题在可计算性理论与计算复杂性理论中，所谓的决定性问题（Decision problem）是一个在某些形式系统回答是或否的问题。例如：**“给两个数字x与y，x是否可以整除y？”**便是决定性问题，此问题可回答是或否，且依据其x与y的值。

决定性问题与功能性问题（Function problem，或复杂型问题）密切相关，功能性问题的答案内容，较简单的是与非复杂许多。范例问题：“给予一个正整数x，则哪些数可整除x？”

另一个与上述两类问题相关的是最佳化问题（Optimization problem），此问题关心的是寻找特定问题的最佳答案。

解决决定性问题的方法称为决策程式或算法。一个针对决定性问题的算法将说明给予参数x和y的情况下如何决定x是否整除y。若是某些决定性问题可以被一些算法所解决，则称此问题可决定。

计算复杂度的领域中，分类可决定问题的依据在于此问题有多难被解决。在此标准下，所谓的难是以解决某问题最有效率的算法所花费的计算资源为依据。在递回理论中，非决定性问题由图灵度决定，指的是一种在任何解答中隐含的不可计算性量词。

计算性理论的研究集中在决定性问题上。在与功能性问题的等值问题中，并没有失去其普遍性。1

相关条目最佳化问题

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学