函數問題 在计算复杂性理论内函数问题英語Function problem或者功能性问题是一种计算问题英语computational problem对任何一种输入都预期会有单一个输出但是输出不像是决定性问题一样这么单纯换句话说输出不只是或否比决策问题复杂得多重要的范例像是旅行推销员问题询问一张图是否有可以绕过每一点的不重复路径输出为路径以及整数分解输出为输入的质因数 因为没有明显类比的语言函数问题比起决定型问题要难以研究而且因为输出的可能变多在解决输入输出之间的转换函数问题归约的过程也比较微妙函数问题也可以用像是决定性问题的方式来分成各种复杂度类举例来说FP是指可以用确定型图灵机在多项式时间里面可以解决的函数问题类似于决定性问题的P而FNP是指可以用非确定型图灵机在多项式时间里面可以解决的函数问题类似于决定性问题的NP 对所有能在多项式时间内解决的的函数问题一定存在一个雷同的决定型问题可以用多项式时间图灵归约将后者归约为前者的方式解决这个函数问题举例旅行推销员问题的决定型问题版本如下 给定一个有权重的有向图和一个整数K是否存在一个哈密顿路径或者哈密顿回路如果问题指定推销员在经过所有城市后一定要回到家并且走过的路径权重相加小于或者等于K 给定这个决定性问题的解答我们则可以解决旅行推销员问题如下 令 n displaystyle n 为边的数量 w i displaystyle wi 则是边 i displaystyle i 的权重首先我们重新设定边的权重给予每个边 i displaystyle i 新的权重 w i     n    w i   i displaystyle winwii 这并不会改变最短路径本身但是会保证这路径是唯一的然后将所有的边权重加起来得到这个图的总权重 M displaystyle M 接着我们使用折半搜索算法找出这条最短路径的权重是否有权重轻于  M   displaystyle M 的路径 是否有权重轻于  M   displaystyle M 的路径 等等找到最短路径的权重 W displaystyle W 之后我们藉由以下演算法确定特定某个边 i displaystyle i 是否在这个路径上修改 i displaystyle i 的权重为 W   displaystyle W 之后询问这个图是否还是有一个权重为 W displaystyle W 的哈密顿路径如果修改后的图里面不存在这条路径则 i displaystyle i 这个边必定在原图的最短路径里面反之如果修改后此路径还是存在则i不在原来的路径之内 这个演算法将旅行推销员问题的时间复杂度放进FPNP内可以在多项式时间之内以决定性图灵机和一个能解决NP问题的神谕解决的问题并且事实上是这个复杂度类的完备问题