功能性问题 编辑
在计算复杂性理论内，功能性问题或者函式问题是一种计算问题，对任何一种输入都预期会有单一个输出，但是输出不像是决定性问题一样这么单纯。换句话说，输出不只YES跟NO。重要的范例像是旅行推销员问题，询问一张图是否有可以绕过每一点的不重复路径，以及整数分解，输出为输入的质因数。
4
图片 0 图片
评论 0 评论
匿名用户 · [[ show_time(comment.timestamp) ]]
[[ nltobr(comment.content) ]]
相关
图灵归约是可计算性理论中的一种归约，若问题A可图灵归约成问题B，是指若问题B的解答已经知道，就可以解问题A，也可以解释为若一个算法可以用来处理问题B，就可以处理问题A。较正式的说法，可被图灵归约成问题B的问题是指若存在问题B的预言机，就可以求解的问题集合。图灵归约可以用在决定性问题及功能性问题。
在计算复杂度理论内，NP-易这个复杂度类是使用带有在NP里面某个决定性问题神谕的图灵机，能在多项式时间内解决掉的功能性问题。
在计算复杂度理论内，NP-易这个复杂度类是使用带有在NP里面某个决定性问题神谕的图灵机，能在多项式时间内解决掉的功能性问题。