這是證明某件事情是否完整的正確理解？

Question

據我所知有兩個步驟來證明一個問題是NP完全性：

1. 給出了一種算法，可以驗證在多項式時間內解決問題。也就是說，一種算法，其輸入是提出的問題解決方案，其輸出是「是」還是「否」，取決於輸入是否是問題的有效解決方案。

2. 證明這個問題是NP難 - 比如，假設你有一個可以在一個步驟計算其它已知的NP完全問題的神諭。使用它，編寫一個在多項式時間內解決這個問題的算法。

例如，假設我們要證明下面的問題是NP完全性：

給定一組整數，S的，是可以分離的元素，S'，使得該子集在S'元素的總和恰好等於未包含在S'剩餘的元素的在S總和？

步驟1：驗證算法

Verify_HalfSubset(Set S, Solution sol): 
    accum = 0 
    for each element i in sol: 
     accum+=i 
     linear search for an element with the same value as i in S. 
     if found, delete it from s, if not found, return false 
    end for 
    accum2 = 0 
    for each element i in S: 
     accum2+=i 
    end for 
    if accum==accum2 return true, else return false 

顯然，這運行在多項式時間：在O(nm)第一個for循環運行，並在O(n)第二運行。

步驟2：還原

假設我們有在單一步驟中計算子集和問題的預言O(Set S, int I)（即是，是否有S中元素總結到I的子集）？

然後，我們可以寫我們的計算一半子集問題的多項式時間算法：

HalfSubset(Set S): 
    accum = 0 
    for each s in S: 
     accum+=S 
    end for 
    if(accum%2==1) 
    // this question forbids "splitting" values to non-integral parts 
     return NO_ANSWER 
    end if 
    half1 = O(S, accum/2) 
    if(half1 == NO_ANSWER) 
     return NO_ANSWER 
    end if 
    for each i in half1: 
     linear search for an element with the same value as half1[i] in S 
     delete it from S. 
    end for 
    half2 = S 
    return (half1 and half2) 

是否有人可以告訴我，如果我做了這個過程中的任何錯誤？這是我期末考試複習中的一個問題，我不完全確定自己完全理解。

Answer 1

你的答案的第二部分是有點過。你在第二步中所說的是，你可以在多項式時間內將這個問題簡化爲已知的NP完全問題。也就是說，你說這個問題最多和NP完全問題一樣困難。

你想說什麼就是NP完全問題可以降低到在多項式時間內你的榜樣的問題。這表明，如果你可以在多項式時間內解決這個問題，那麼你也可以在多項式時間內解決NP完全問題，證明你的例子問題是NP完全的。

Answer 2

不，這是不正確。您可以設置一種情況，即使用NP-Complete oracle來解決問題，但問題本身仍然存在於P.

您需要做的是證明您可以將另一個NP-Complete問題減少到你的問題。也就是說，提供了一個多項式算法，以特定的NP完全問題的任何實例轉換成你的問題的一個實例，使得您的（改變）問題的解決方案也是給定的NP完全問題的解決方案。這表明，如果你能解決你的問題，那麼你也可以解決任何NP-Complete問題，這意味着你的問題至少和其他NP-Complete問題一樣困難。