查看“︁函數問題”︁的源代码

在[[计算复杂性理论]]内，'''函数问题'''（{{lang-en|Function problem}}）或者'''功能性问题'''是一种{{Link-en|计算问题|computational problem}}，对任何一种输入都预期会有单一个输出，但是输出不像是[[决定性问题]]一样这么单纯。换句话说，输出不只''是''或''否''，比决策问题复杂得多。重要的范例像是[[旅行推销员问题]]，询问一张图是否有可以绕过每一点的不重复路径（输出为路径），以及[[整数分解]]，输出为输入的质因数。

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

对所有能在多项式时间内解决的的函数问题，一定存在一个雷同的决定型问题，可以用[[多项式时间图灵归约]]将后者归约为前者的方式，解决这个函数问题。举例，[[旅行推销员问题]]的决定型问题版本如下：

:给定一个有权重的[[有向图]]和一个整数K，是否存在一个哈密顿路径（或者哈密顿回路，如果问题指定推销员在经过所有城市后一定要回到家）并且走过的路径权重相加小于或者等于K？

给定这个决定性问题的解答，我们则可以解决旅行推销员问题如下：

:令<math>n</math>为边的数量，<math>w_i</math>则是边<math>i</math>的权重。首先我们重新设定边的权重，给予每个边<math>i</math>新的权重<math>w'_i = 2^{(n+1)} w_i + 2^i</math>。这并不会改变最短路径本身，但是会保证这路径是唯一的。然后，将所有的边权重加起来，得到这个图的总权重<math>M</math>。接着，我们使用[[折半搜索算法]]找出这条最短路径的权重：是否有权重轻于<math>< M/2</math>的路径？ ；是否有权重轻于<math>< M/4</math>的路径？ …等等。找到最短路径的权重<math>W</math>之后，我们藉由以下演算法确定特定某个边<math>i</math>是否在这个路径上：修改<math>i</math>的权重为<math>W+1</math>之后，询问这个图是否还是有一个权重为<math>W</math>的哈密顿路径？如果修改后的图里面不存在这条路径，则<math>i</math>这个边必定在原图的最短路径里面，反之，如果修改后此路径还是存在，则i不在原来的路径之内。

这个演算法将旅行推销员问题的时间复杂度放进FP<sup>NP</sup>内（可以在多项式时间之内，以决定性图灵机和一个能解决NP问题的[[谕示机|神谕]]解决的问题），并且事实上是这个复杂度类的[[完备(复杂度)|完备]]问题。

==参考资料==
{{refbegin}}
* Raymond Greenlaw, H. James Hoover, ''Fundamentals of the theory of computation: principles and practice'', Morgan Kaufmann, 1998, ISBN 155860474X, p. 45-51
* Elaine Rich, ''Automata, computability and complexity: theory and applications'', Prentice Hall, 2008, ISBN 0132288060, section 28.10 "The problem classes FP and FNP", pp. 689-694
{{refend}}

== 参见 ==
* [[决策问题]]
* [[搜索问题]]
* {{Link-en|计数问题|Counting problem (complexity)}}
* [[最佳化问题]]

[[Category:计算复杂性理论]]