跳转到内容

承诺问题

维基百科,自由的百科全书

计算复杂度理论里,承诺问题是一类决定性问题,其可接受输入是一个确定大小的集合。[1]与其他的决定性问题不同,承诺问题接受的输入(确定输出会是或者的输入)并不包含所有可能的输入。直觉上,我们可以说输入的承诺是在一群的输入或的输入里面。如果输入不属于这两个集合,那么此算法允许输出任何答复。

正式定义

一个决定性问题可以说与一个语言互通,这问题接受所有在里面的输入,拒绝所有不在里面的输入。承诺问题则是与两个语言相关, and 。此两个语言一定不交集,换句话说,。此承诺问题接受所有在里面的输入,拒绝所有在里面的输入。的集合则是此问题的承诺。对于不属于承诺里面的输入则没有规定输出必须是什么。如果承诺等于,此承诺问题同时也是决定性问题。

范例

许多自然的问题实际上是承诺问题。举例来说,考虑以下问题:给予一个有向图,决定此图是否有长度为10的道路。这问题回答为的输入是有长度为10道路的有向图,回答的输入是所没有长度为10道路的有向图,承诺范围则是所有的有向图。在这个例子里面,检查输入是否在承诺范围里面是比较简单的,不过有一些问题可能承诺范围是很难计算的。举例,考虑此问题:"给定一个哈密顿图,检查是否有大小为4的循环" ,检查输入是否是哈密顿图是一个NP-hard问题,但是检查是否有大小为4的循环则只需要多项式时间。

相关条目

参考资料

  1. ^ Promise problem 互联网档案馆存档,存档日期2010-07-27. at the Complexity Zoo.

研究