1樓：陳世騰
不是的。正如其他一些答主說的，還需要P2屬於NP。乙個很簡單的反例就是3-UNSAT問題，就是問乙個3-CNF是否不可滿足。
很顯然，這個問題和3-SAT可以互相規約。但是它不屬於NP，所以不是NP-complete的。事實上它是co-NP-complete的。
準確的說，不能說不屬於NP吧。因為我們現在還不知道NP和co-NP是否相等。但是應該複雜性理論這邊的主流還是相信兩者不等的。
2樓：少十七
另外乙個回答說到要證明P2屬於NP，
除此之外, 還需要證明 I2 存在乙個 witness w2,...按照定義 Karp reduction 並不需要保證這個性質.
這不是直接靠定義，顯然的麼？
首先這裡面的多項式時間規約，我認為指的是Karp reduction，否則如果是Turing reduction的話，結論顯然不成立，比如 。（這裡我說得並不嚴謹，畢竟我們也不知道NP和co-NP是不是相等。）
下面我們就證明如下命題：如果A可以Karp規約到B，並且B屬於NP，那麼A也屬於NP。
先給出NP的定義，這裡我們選取用witness定義的方式：
是乙個NP問題是指：如果存在乙個多項式時間的圖靈機 ，乙個多項式 使得對任意的字串 ，
. （1） 這裡|x|表示x的長度。
再給出Karp reduction的定義，
問題A可以 Karp 規約到問題B是指： 如果存在乙個多項式時間可計算的函式 使得對任意的，
2）下面我們開始證明：
因為B屬於NP，由定義，存在乙個多項式時間的圖靈機，以及乙個多項式滿足要求（1）。
又因為A可以Karp規約到B，由定義，存在乙個多項式時間可計算的函式滿足要求（2）。
下面我們構造這樣乙個多項式時間的圖靈機 ，
因為和 都是多項式時間可計算的，顯然也是多項式時間可計算的。
此外，由於是多項式時間可計算的，存在乙個多項式 使得對任意的。
我們取 ，顯然是乙個多項式。
下面我們就證明，對任意的 ，和 滿足要求（1），即
這裡 整體被看做乙個witness.
由左推右：
如果 , 則由 Karp 規約 . 記 ，我們有 .
又因為B屬於NP，由定義，存在乙個 使得 ， 並且 .
所以，並且，由的定義，因為以及 ， 我們有 .
由右推左：
，由的定義， 我們有 .
因為B屬於NP， 推出 , 即 .
由Karp規約的定義， 推出 .
我盡量把細節都寫下來了，可能看著有點繁瑣，本質上這就是乙個由定義直接推出的結論。
好了，下面是習題：
試用NP的非確定型圖靈機（Nondeterministic Turing machine）定義證明以上結論。
3樓：
回到題主的問題, 假設這裡都是 Karp reduction, 那麼顯然 p2 是 NP-hard 的. 現在的問題是 p2 的 NP-containment.
（省得你們 NLP 解析失敗，下面兩段是在試著證 p2 的 NP-containment，結論是證不出來）
給定乙個 p2 的 instance I2, 可以用 Karp reduction 寫出乙個 p1 的 instance I1. 但是 p1 的 NP-containment 只是說存在乙個 witness w1 (關於 instance I1) 使得有確定性多項式時間演算法能夠判斷 yes/no.
除此之外, 還需要證明 I2 存在乙個 witness w2, 能夠高效地對映到 p1 的 NP-containment 需要的 w1 上. 按照定義 Karp reduction 並不需要保證這個性質.
雅思口語P1，P3比較順利沒有打斷，p2說了大概一分鐘說不下去了在思考中被打斷？5 5能不能有？
這個應該有。如果P3回答比較順利而且語法等低階錯誤較少的話，我覺得是可以有5.5的。據傳打分是這樣的，第一部分結束後，考官會給個基礎分，這個不會高於5.5 第二部分再決定你有沒有6 第三部分決定你能不能拿到6.5 第二部分如果只是思路問題而表達沒有問題的話 而且也說了一分鐘嘛 考官會參考趴三，如果趴...
P2P理財常見問題？
銅小喵 1 什麼是P2P網貸?答 借款人通過線上平台在網上發布借款標並給投資人利息來獲得融資，投資人通過出借資金獲得收益，平台是中介，為投資人審核借款專案。2 P2P網貸理財違法嗎?答 當前，中國法律尚沒有對網際網路金融的明確規定，因此，我們僅將P2P平台定義於民間借貸，需要注意的是，若故意以高利率...
請問這個c 指標問題中的p2為什麼是最後這樣的結果
shzy 邱昊宇的回答比較細。我簡單的講講。首先想乙個問題，為什麼printf函式穿的是值，scanf函式傳的是位址。因為c c 裡，所有的函式呼叫都是 值傳遞 或者說 值拷貝 值構造 暫不提引用 所以為什麼要有指標，因為如果你想改變乙個變數的值，你就只有傳他的位址。如果你想改變乙個指標的值，那就傳...