功能性问题

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

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

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

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

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

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

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