函數問題

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

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

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

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

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

为边的数量,则是边的权重。首先我们重新设定边的权重,给予每个边新的权重。这并不会改变最短路径本身,但是会保证这路径是唯一的。然后,将所有的边权重加起来,得到这个图的总权重。接着,我们使用折半搜索算法找出这条最短路径的权重:是否有权重轻于的路径? ;是否有权重轻于的路径? …等等。找到最短路径的权重之后,我们藉由以下演算法确定特定某个边是否在这个路径上:修改的权重为之后,询问这个图是否还是有一个权重为的哈密顿路径?如果修改后的图里面不存在这条路径,则这个边必定在原图的最短路径里面,反之,如果修改后此路径还是存在,则i不在原来的路径之内。

这个演算法将旅行推销员问题的时间复杂度放进FPNP内(可以在多项式时间之内,以决定性图灵机和一个能解决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

参见