函数问题

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

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

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

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

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

令

n

为边的数量，

w_{i}

则是边

i

的权重。首先我们重新设定边的权重，给予每个边

i

新的权重

w'_{i}=2^{(n+1)}w_{i}+2^{i}

。这并不会改变最短路径本身，但是会保证这路径是唯一的。然后，将所有的边权重加起来，得到这个图的总权重

M

。接着，我们使用折半搜索算法找出这条最短路径的权重：是否有权重轻于

<M/2

的路径？；是否有权重轻于

<M/4

的路径？ …等等。找到最短路径的权重

W

之后，我们借由以下算法确定特定某个边

i

是否在这个路径上：修改

i

的权重为

W+1

之后，询问这个图是否还是有一个权重为

W

的哈密顿路径？如果修改后的图里面不存在这条路径，则

i

这个边必定在原图的最短路径里面，反之，如果修改后此路径还是存在，则i不在原来的路径之内。

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

参考资料

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

参见