功能性问题

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

因为没有明显类比的语言,功能性问题比起决定型问题要难以研究。而且因为输出的可能变多,在解决输入输出之间的转换,功能性问题归约的过程也比较微妙。功能性问题也可以用像是决定性问题的方式来分成各种复杂度类。举例来说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, 编辑

    最佳化问题