减少功能是否对应？

Question

我正在学习可编程性和复杂性，并且我怀疑是否有问题。 将问题减少到另一个问题的函数是图灵算法。我想知道是否它甚至是一个一对一的函数（对应），例如，查看顶点覆盖 - >独立集减法，我看不到一个问题的实例不与另一个实例相对应另一个。

谢谢

Answer 1

不，没有一对一的对应关系。如果您将问题A减少到问题B，例如在多项式时间内（A < = _pol B），这意味着您可以通过问题B的解决方案来解决问题A.但是可能有一个输入用于问题B无法用A的解决方案求解。此外，还原函数可以将问题A的多个输入映射到问题B的单个输入。

例如，将子集（G，k）还原为子图异构（G ，H）：Clique < = _pol子图同构。一个集团只是一个特殊的子图H，你可以用k多项式构造它。但是为了能够解决Clique（G，k）不会帮助你在G中找到任意子图H.因此，并非SubgraphIsomorphism的每个输入都对应于Clique的输入。这种减少仅仅表明子图同构至少与Clique一样困难。