證明融通α的問題是NP

Question

試圖刷上計算的理論，但我不知道的解決這個：

Prove that the problem of factoring α is in NP. 

我有一種感覺，可能涉及到找到一個NP問題，尋找α因子分解問題的減少。

Answer 1

實際上這很簡單。乘法在P中。NP與「檢查所有可能的並行多項式大小解決方案」相同。如果alpha被編碼爲長度爲n的比特串，則因子總長度最多爲n + c。

它不是「NP-complete」。沒有辦法將任意的NP問題轉化爲保理。

Answer 2

問題P中：是一個問題，那就是通過確定性圖靈機可計算在多項式時間 問題在NP：是一個問題，是臨屋polynomicaly veryfiable通過確定性圖靈機。在NP中，我們以這種方式使用非確定性，即只需要一個計算樹的一個分支被接受（我們在「相同」時間嘗試「所有」可能性）。多項式非常易於表示，我們有一個證書（讓它成爲c），這是輸入詞的解決方案（讓它成爲w）。證書必須是考慮輸入長度的多項式長度。我們的任務只是驗證證書是否是解決方案。例如，在SAT（滿足性問題）中，證書是正確的分配（這是非確定性猜測）。

所以你證明你的問題是在NP： 存在一個DTM驗證一對（w，c），其中w是輸入數字，c是它的因子。你必須建立一個在c中乘以因子並將其與w進行比較的更好的方法。