我正在研究可计算性和复杂性，但我有一个疑问。将问题简化为另一个问题的功能是图灵可计算的。我想知道它是否甚至是一对一的函数（对应），因为例如查看 Vertex-Cover -> Independent Set reduction 我看不到一个问题的实例与另一个实例不对应的位置另一个。
谢谢
问问题
57 次
1 回答
1
不，没有一对一的通信。如果您将问题 A 简化为问题 B，例如在多项式时间内 (A <=_pol B)，这意味着您可以借助问题 B 的解决方案来解决问题 A。但是可能有一个输入问题 B 你不能用 A 的解决方案来解决。归约函数也可以将问题 A 的多个输入映射到问题 B 的单个输入。
以 Clique(G,k) 简化为 SubgraphIsomorphism(G,H) 为例：Clique <=_pol SubgraphIsomorphism。一个集团只是一个特殊的子图 H，你可以在 k 中按时间多项式构造。但是能够解决 Clique(G,k) 不会帮助您在 G 中找到任意子图 H。因此，并非 SubgraphIsomorphism 的每个输入都对应于 Clique 的输入。这种简化仅表明 SubgraphIsomorphism 至少与 Clique 一样难。
于 2015-08-03T11:50:16.610 回答