減少功能是否對應？

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一樣困難。